Hien Thi

Thu Truong

Claudia-Lavinia Ignat

Pascal Molli
email: pascal.molli@acm.org

Authenticating Operation-based History in Collaborative Systems

Keywords: K.6.5 [Security and Protection]: [Authentication], H.5.3 [Group and Organization Interfaces]: [Computer-supported cooperative work], C.2.4 [Distributed Systems]: [Distributed applications] authenticating logs, multi-synchronous collaboration, authenticators, optimistic replication, logs, operation-based history

Within last years multi-synchronous collaborative editing systems became widely used. Multi-synchronous collaboration maintains multiple, simultaneous streams of activity which continually diverge and synchronized. These streams of activity are represented by means of logs of operations, i.e. user modifications. A malicious user might tamper his log of operations. At the moment of synchronization with other streams, the tampered log might generate wrong results. In this paper, we propose a solution relying on hash-chain based authenticators for authenticating logs that ensure the authenticity, the integrity of logs, and the user accountability. We present algorithms to construct authenticators and verify logs. We prove their correctness and provide theoretical and practical evaluations.

INTRODUCTION

Collaboration is a key requirement of teams of individuals working together towards some common goal. In recent years collaborative editing systems such as wikis, GoogleDocs and version control systems became very popular. These systems rely on a multi-synchronous collaboration model [START_REF] Dourish | The parting of the ways: divergence, data management and collaborative work[END_REF][START_REF] Ignat | Providing Awareness in Multi-synchronous Collaboration Without Compromising Privacy[END_REF] that allows users to work simultaneously on shared documents following some cycles of divergence and convergence. Copies of the shared data diverge when users work in isolation and converge later when users synchronize their changes.

The mechanism, that allows replicas to diverge during a time interval ensuring that they will eventually converge at a later time, is called optimistic replication [START_REF] Saito | Optimistic replication[END_REF]. Optimistic replication can be classified into state-based and operation-based [START_REF] Lippe | Operation-based merging[END_REF]. In statebased replication each site applies updates to its replica without maintaining a change log. Usually in systems adopting state-based replication such as Active Directory in Windows Server and Coda file system [START_REF] Satyanarayanan | Coda: A highly available file system for a distributed workstation environment[END_REF], every site sends its local state to other sites that can merge the received state with their own states. Systems that use operation-based replication such as Bayou [START_REF] Petersen | Flexible update propagation for weakly consistent replication[END_REF], IceCube [START_REF] Kermarrec | The icecube approach to the reconciliation of divergent replicas[END_REF] and GoogleDocs keep modifications performed on a replica in a history which is then sent to other replicas. Operation-based approaches are used when the cost to transfer state is high such as in database systems or mobile systems; and when operation-semantics is important. In this work we target systems that use operation-based replication.

In operation-based replication systems users can misbehave by tampering history for their convenience. For instance, they can remove some content of the history or change the order of some operations from the history. This might be critical for some collaborative systems such as version control systems. It is vitally important to be able to retrieve and run different versions of a software. If the history can be modified, revisions do not correspond to the expected behavior of the software. Moreover, developers cannot be made responsible for the revisions for which they contributed. Furthermore, by modifying the history, a contributor may introduce security holes in the system under the name of another contributor. Therefore, there is a need to ensure integrity of the log, and in case the log was tampered, the misbehaving user should be detected.

Solutions for securing logs can be classified into two main families: non-cryptographic secure logging and cryptographic secure logging. The former approach is based on a secure logging machine such as a write-only medium (e.g CD/DVD), a tamper-resistanthardware or a trusted hardware to prevent adversary from modifying logs [START_REF] Chong | Secure audit logging with tamper-resistant hardware[END_REF]. However, in real-world applications deployed over large scale distributed environments, it is impractical to assume the presence of such devices. The later approach has been investigated deeply with numerously extensive research (namely, [START_REF] Greenberg | Personalizable groupware: accommodating individual roles and group differences[END_REF][START_REF] Greenberg | Human and technical factors of distributed group drawing tools[END_REF][START_REF] Crosby | Efficient data structures for tamper-evident logging[END_REF][START_REF] Davis | Time-Scoped Searching of Encrypted Audit Logs[END_REF][START_REF] Hasan | The case of the fake picasso: Preventing history forgery with secure provenance[END_REF][START_REF] Holt | Logcrypt: forward security and public verification for secure audit logs[END_REF][START_REF] Ma | A new approach to secure logging[END_REF][START_REF] Maniatis | Secure history preservation through timeline entanglement[END_REF][START_REF] Schneier | Cryptographic support for secure logs on untrusted machines[END_REF][START_REF] Yavuz | Baf: An efficient publicly verifiable secure audit logging scheme for distributed systems[END_REF]). These existing solutions, however, are adapted only for collaboration based on a single global stream of activity over shared data. For instance, floor control policies [START_REF] Greenberg | Personalizable groupware: accommodating individual roles and group differences[END_REF] and locking mechanisms [START_REF] Greenberg | Human and technical factors of distributed group drawing tools[END_REF] ensure a single global stream of activity by allowing a single user at a time to access objects in the shared workspace.

Multi-synchronous collaboration abandons constructing a single stream of activity out of the history of all user activities. Instead, it maintains multiple, simultaneous streams of activity, and then manages divergence between these streams. Each user maintains therefore different streams of the global history containing activity of all users. Throughout this paper we call logs standing for these different streams of activity. The main challenge that we address in this paper is how to secure logs in the multi-synchronous collaboration. To our best knowledge, no existing work addressed this issue.

In this paper, we propose a solution relying on hash-chain based authenticators for securing logs in multi-synchronous collaboration. The proposed authenticators ensure the authenticity and the integrity of the logs, i.e. any log tampering is detectable. Moreover, the proposed authenticators provide user accountability, i.e. any user can be made accountable of her misbehavior on log tampering.

The paper is structured as follows. We start with a context for our work in Section 2. We then go on by presenting in Section 3 a threat model and desirable properties our proposal tackles. We next describe in Section 4 our proposed approach based on authenticators including their definitions and examples of how they are constructed. In Section 5, we present our algorithms to construct authenticators and verify logs, and proofs of their correctness. We provide an evaluation with real collaboration histories from projects using Mercurial and an analysis showing the feasibility of our proposal in Section 6. We give an overview of related works in Section 7. In Section 8, we end the paper with some concluding remarks.

CONTEXT

Push-Pull-Clone (PPC) is the most general paradigm supporting multi-synchronous collaboration. Users work simultaneously on different streams of activity on the shared data. In the PPC model, users replicate shared data, modify it and redistribute modified versions of this data by using the primitives push, pull and clone. These primitives are used for managing divergence and convergence of different streams of activity. To start, users clone shared data and maintain in a local workspace this data as well as modifications done on this data. Users can then push their changes to different channels at any time they want, and other users that have granted rights may pull these changes from these channels. By using pull primitives, replicas are synchronized. In Figure 1, an instantiation of the PPC model with three users is illustrated. In this figure, user 1 and user 2 interact with each other by using push and pull primitives, while user 3 performs a clone from user 2. The PPC collaboration model is very widely used in distributed version control systems such as Git, Mercurial and Darcs. It is a very general collaboration model without a collaboration provider where users share their data only with people whom they trust. PPC model generalizes the collaboration model with a service provider where users interact only with a server that forwards afterward the changes to the other users. We consider the operation-based collaboration where user changes are kept in a log that is then sent to the other users and logs are merged at synchronizations. We consider a system with a number of sites which can operate independently on replicas of shared documents. Each site keeps the shared document as a log of operations that have been performed during a collaborative process, L = [op 1 , op 2 , ..., op n ]. Each operation is parameterized depending on an application domain. A shared document can be as large as a database (i.e. Bayou) or as small as a single file. Operations can be treated at different granularities ranging from characters, lines or paragraphs in a document to deltas between revisions. A document is created at one site and replicated to other sites by means of push and clone primitives. Sites store operations in their logs in an order that is consistent with the order they were generated.

The order of addition of operations in the log is compatible with the "happened-before" relation between operations [START_REF] Lamport | Time, Clocks, and the Ordering of Events in a Distributed System[END_REF]. We say that op a happened-before op b , denoted as op a op b , if op b was generated on some site after op a was either generated or received by that site. The "happened-before" relation is transitive, irreflexive and antisymmetric. Two operations op a and op b are said concurrent if neither op a op b nor op b op a . Changes on the shared document made by users are propagated in weakly consistent manner from one site to another site. Users decide by means of primitives push and pull when, with whom and what data to be sent and synchronized. When a pull is performed by user 1 from the channel where user 2 pushed his changes, in order to minimize traffic overhead, an anti-entropy mechanism is used [START_REF] Demers | Epidemic Algorithms for Replicated Database Maintenance[END_REF]. Only the part of the log of user 2, that is new to user 1 since the last time that two users synchronized, is sent to user 1. The remote log from user 2 is synchronized with the local log of user 1. The synchronization mechanism requires to detect the concurrency and happened-before order between changes of different sites. Also the conflicts between concurrent changes must be resolved. Replicas are consistent if their states are identical when they have applied the same set of operations. For our approach, we use the CRDT family of algorithms [START_REF] Preguiça | A commutative replicated data type for cooperative editing[END_REF][START_REF] Weiss | Logoot-Undo: Distributed Collaborative Editing System on P2P Networks[END_REF] which design operations to be commutative from the start. When reconciliation is performed, operations from the remote log, that have not been previously integrated into the local log, are simply appended to the end of the local log. The log propagation mechanism uses anti-entropy which preserves happened-before order between operations. Therefore, the reconciliation mechanism ensures happened-before order between operations as well as it allows concurrent operations to appear in logs in variant orders.

We define a partially ordered set (poset) H = (P, ) where P is a ground set of operations and " " is the happened-before relation between two operations of P, in which " " is irreflexive and transitive. We call H as an operation-based history in our context. Given a partial order " " over a poset H, we can extend it to a total order "< t " with which "< t " is a linear order and for every x and y in H, if x y then x < t y. A linear extension L of H is a relation (P, < t ) such that: (1) for all op 1 , op 2 in P, either op 1 < t op 2 or op 2 < t op 1 ; and (2) if op 1 op 2 then op 1 < t op 2 . This total order preserves the order of operations from a partial order set H to the linear extensions on the same ground set P.

We call these linear extensions as individual logs observed by different sites. The Figure 2 shows an example of a history and its linear extensions.

In collaborative systems, where multiple sites collaborate on the same shared data object, we can consider that the global stream of activity of all sites is defined by a partially ordered set of operations. Each site, however, can see only operations in his workspace that it generated locally or received from other sites. The site keeps therefore an individual log as a linearization of history built on a subset of a ground set of operations. There are remaining operations of global history built on entire ground set of operations that are not visible for the site.

SECURITY ASPECTS

In operation-based collaborative systems, authentication of data items for collaborative workflows has gained increasing importance. Say for example, if Tom receives a document from Olivia and processes a part of it and then forwards to Pierre, the operationbased document should include the chronological log of actions that each user, Tom, Olivia and Pierre, performed on the document. The correctness of collaboration outcome is based on the trustworthiness of users who maintain the history of versions. Unfortunately, a malicious user can always introduce phony updates to forge history or alter the correct order of versions. This attack raises the threat that honest users might get forged content of shared data. Replicas with corrupted updates might never converge with other valid replicas and this is critical in replication systems. This section presents a threat model followed by desirable properties for dealing with security requirements.

Threat Model

A threat model, which models the capabilities of attackers, is necessary to analyze the threats that will be addressed by our solution.

There are two types of malicious users: insiders and outsiders. We consider in this paper an inside adversary who has full rights to access a replicated object. Such an adversary might want to alter the history including actions performed on data by authorized contributors. For example, when Tom provides a document to Olivia who can perform and contribute new updates to the document, she should not be able to modify actions that Tom performed which were recorded in log.

We assume users trust each other with their social-based relationship when they start to collaborate. However, trust it not immutable and trusted users once they gained access to the log can always misbehave. Such an active attacker can read, (over)write, delete and change order of log entries. In doing so, an attacker alters existing records or adds forged information to history.

Our work assumes only adversaries who act inside of the system. We cannot prevent outsider attacks where an adversary copies data to create a new document and claims at a later time as being an owner. This might be possible in our system if an adversary removes completely the log of operations, which corresponds to a document removal. We could deal with outsider attacks with the support of a trusted platform, however, we exclude this assumption in our collaborative system.

Desirable Properties

The following properties are addressed to authenticate operationbased history in collaborative systems.

Integrity. Adversaries are infeasible to forge a log, such as modify its entries or put new forged operations into log, without being detected. Integrity is the most important property required for securing logs in operation-based replication. Ensuring the integrity of a single document can be done easily by using cryptographic signatures or checksums. However, ensuring the integrity of a replicated document represented by a log of operations is more difficult as operations cross multi-contributors and some of them might be adversaries.

Concurrency-collision-freeness. In a history H, some operations might be concurrent, while some others might be in a happenedbefore relation. If L i and L j are different linearizations of the same history H then any authentication mechanism applied to L i and L j should yield the same result. The "yielding the same result" is expressed by the concurrency-collision-freeness property: the authentication mechanism holds a function f that f

(L i ) = f(L j ) ∀L i , L j ∈ H.
The "concurrency-collision-freeness" property should be guaranteed in authenticating logs.

In Figure 2, we give an example of a history which is linearized into two logs by two sites. The history H, which is built on the ground set of operations P = {op 0 , op 1 , op 2 , op 3 , op 4 , op 5 , op 6 } with " " relation, is recorded in logs, L 1 = {op 0 , op 1 , op 2 , op 3 , op 5 , op 4 , op 6 } and L 2 = {op 0 , op 2 , op 4 , op 1 , op 3 , op 6 , op 5 }. They both preserve orders of all operations of the history H. In order to fulfill concurrency-collision-free property, any authentication mechanism applied to L 1 and L 2 should yield the same result. If the authentication results are different, then it means that one of the logs was tampered.

Forward-aggregated authenticity. While logs grow, log verifiers can skip verification of log entries which have been already authenticated. The authentication mechanism should allow accumulation of log verification for a time interval. Not only the integrity of individual log entries but also the integrity of the whole log stream should be preserved. This forward-aggregated authenticity property is similar to forward security and append-only property investigated in many existing works of secure log audit [START_REF] Abdalla | A new forward-secure digital signature scheme[END_REF][START_REF] Ma | Extended abstract: Forward-secure sequential aggregate authentication[END_REF][START_REF] Yavuz | Baf: An efficient publicly verifiable secure audit logging scheme for distributed systems[END_REF].

Public verifiability. This property allows any user in a collaborative system to verify the integrity of logs. Adversaries are made accountable for unauthorized actions. This property can be done by using digital signatures such as RSA or DSA signature scheme. Public verifiability is especially desirable in distributed collaborative systems where logs need to be audited by any collaborator without relying on any trusted central authority.

AUTHENTICATORS

In this section, we present our approach to construct authenticators T @site to deter users from log tampering while preserving the above mentioned properties.

When a sending site sends a document to a receiving site, it creates an authenticator for its log. The authenticator is attached to the sent document. The receiving site creates a new authenticator when it receives the document. We assume each site involved in this push-pull communication possesses a cryptographic public/private key pair that is assigned to a unique site identifier and that all users can retrieve the public key of each other. This assumption is reasonable in practice [START_REF] Walsh | Experience with an Object Reputation System for Peer-to-Peer Filesharing (Awarded Best Paper)[END_REF][START_REF] Mella | Controlled and cooperative updates of xml documents in byzantine and failure-prone distributed systems[END_REF]. The private key of the key pair is used to sign entries of log that prevent malicious sites modifying operations on behalf of other sites. Though sites can choose a public key pair on their-own, to limit Sybil attacks [START_REF] Douceur | The sybil attack[END_REF] we can require that each site possesses a digital certificate from trusted certification authority or has an offline channel (such as email) to identify the owner of public keys. In either case the certification authority plays no role in the process of authenticator creation, and it is used only during initial phase when a site joins the system. We also use cryptographic hash function with properties collision-resistant (it should be difficult to find two different messages m 1 and m 2 such that hash(m 1 ) = hash(m 2 )) and preimage-resistant (with a given hash value h, it should be difficult to find any message m such that hash(m) = h). The collision-resistant property can be used to establish the uniqueness of logs at a certain moment when an authenticator is created.

Definitions

An authenticator is a log tamper-evident which captures a subsequence of operation(s) of a log that were generated in one updating session. An updating session at one user's site is the session between two subsequent push/pull primitives to/from other sites. For example, consider that during a working session, user U generates a log [op 1 , op 2 ] where op 1 op 2 . When user U pushes his changes, he creates an authenticator for the sequence of operations in the log that their orders should not be tampered by any other user. For instance, a receiver of this log should not be able to re-order op 1 and op 2 to change the happened-before order of op 1 and op 2 .

Definition 1. An authenticator, denoted as T @site , is defined as a tuple ID, SIG, IDE, PRE, SYN where: ID: identifier of authenticator which is a tuple < siteID, opID > where siteID is the identifier of the site which creates the authenticator and opID is the operation identifier(s) that the authenticator is linked to; SIG: the value of signature signed by the private key of the site; IDE: a list of operation identifiers used to compute SIG; PRE, SYN: identifiers of preceding and receiving authenticators.

Definition 2. The SIG of an authenticator T @site at a certain update is computed as a signature of a cumulative hash by a sender S or a receiver R, where the sender computes SIG of the most recent authenticator T m @S .SIG = σ S (hash(T m-1 @S .SIG || E)) with condition that E = ∅; and the receiver computes T n @R = σ R (hash (T n-1 @R .SIG || E || T m @S .SIG) with the condition that there exists new update(s) from S appended to log of R, where: T m @S : the most recent authenticator committed by sender S; T n @R : the most recent authenticator committed by receiver R; T m-1 @S : the preceding authenticator of T m @S ; T n-1 @R : the preceding authenticator of T n @R ; E = [op i 1 , op i 2 , ..., op i r ]: subsequent changes generated after preceding authenticator; σ site (•) denotes the signature of site and || denotes the concatenation of arguments used in hashing, where hashing can be done using any traditional hash function such as SHA-256).

The structure of an authenticator is illustrated in Figure 3. When a user shares a document by sending the whole log, she creates an authenticator for log operations computed based on the preceding authenticator and new updated operations. The authenticator is signed by her private key and linked to the last operation of the log. At the receiving site, the receiver performs reconciliation and creates a new authenticator at the reception.

The authenticators of a log of operations are constructed whenever a site sends or receives a new change to/from another site. An authenticator is created in following cases:

• A site sends new changes to other sites. In this case, if a site sends a document without new changes, no new authenticator is needed.

• A site receives new changes from other sites. In this case, the receiving site will check the remote log, detect and resolve conflicts (if there are some conflicts among operations). After these actions, if there are new changes that are added to the receiver's log, a new authenticator is created for this reception.

Example

We use the example of history in Figure 2 where two sites collaborate on a shared document having initial version V 0 |{op 0 } to illustrate the construction of authenticators. We assume that the initial version of the document V 0 consisting of operation op 0 was created by some site among collaborating sites. We further assume that all collaborators agreed on this initial version and that the corresponding log of this initial version does not need to be authenticated. Each of the two sites in our example performs parallel contributions based on the initial version of the document. In the example, site 1 creates the new version V 1 |{op 0 , op 1 } and site 2 creates V 2 |{op 0 , op 2 } concurrently. At a later time, site 1 reconciles with updates from site 2 and creates the up-to-date version V 3 | {op 0 , op 1 , op 2 , op 3 }. In Figure 4, the two sites, site 1 and site 2, will create authenticators to authenticate their logs each time they do pushing or pulling. In what follows we describe in detail how authenticators are constructed. T 1 @site 2 T 1 @site 1 T 2 @site 1 T 2 @site 2 T 3 @site 1 T 3 @site 2 T 4 @site 2 Firstly, when site 2 pushes his log to site 1, it creates an authenticator T 1 @site2 where:

T 1 @site2 .ID = < site2, op 2 > (linked to op 2 ), T 1 @site2 .SIG = σ site2 (hash(∅ || op 0 || op 2 )) T 1 @site2 .IDE = [op 0 , op 2 ] T 1 @site2 .PRE = ∅ (no previous authenticator) T 1 @site2 .SYN = ∅ (no received remote authenticator) When site 1 pulls changes from site 2 and receives the log from site 2, it creates an authenticator T 1 @site1 where:

T 1 @site1 .ID = < site1, {op 1 , op 2 } > (linked to op 1 , op 2 ), T 1 @site1 .SIG = σ site1 (hash(∅ || op 0 || op 1 || T 1 @site2 .SIG)), T 1 @site1 .IDE = [op 0 , op 1 ], T 1 @site1 .PRE = ∅ (no previous authenticator), T 1 @site1 .SYN = T 1 @site2 .ID The two sites site 1 and site 2 then work concurrently and generate the new changes op 3 and op 4 respectively. When site 1 pushes his changes and site 2 pulls those changes, two authenticators T 2 @site1 and T 2 @site2 are constructed. The structure of T 2 @site1 is given below: T 2 @site1 .ID = < site1, op 3 > (linked to op 3 ), T 2 @site1 .SIG = σ site1 (hash(T 1 @site1 .SIG || op 3 )), T 2 @site1 .IDE = [op 3 ], T 2 @site1 .PRE = T 1 @site1 .ID, T 2 @site1 .SYN = ∅ Similarly, T 2 @site2 is computed where: T 2 @site2 .ID = < site2, {op 3 , op 4 } > (linked to op 3 , op 4 ), T 2 @site2 .SIG = σ site2 (hash(T 1 @site2 .SIG || op 4 || T 2 @site1 .SIG)), T 2 @site2 .IDE = [op 4 ], T 2 @site2 .PRE = T 1 @site2 .ID, T 2 @site2 .SYN = T 2 @site1 .ID Again, site 1 and site 2 contribute independently to the document, op 5 is generated by site 1 and op 6 is generated by site 2. The two sites then exchange their changes with each other by pushing and pulling other changes. New authenticators are computed at each site. site 2 computes T 3 @site2 where:

T 3 @site2 .ID = < site2, op 6 > (linked to op 6 ), T 3 @site2 .SIG = σ site2 (hash(T 2 @site2 .SIG || op 6 )), T 3 @site2 .IDE = [op 6 ], T 3 @site2 .PRE = T 2 @site2 .ID, T 3 @site2 .SYN = ∅ site 1 computes T 3 @site1 where: T 3 @site1 .ID = < site1, {op 5 , op 6 } > (linked to op 5 , op 6 ), T 3 @site1 .SIG = σ site1 (hash(T 2 @site1 .SIG || op 5 || T 3 @site2 .SIG)), T 3 @site1 .IDE = [op 5 ], T 3 @site1 .PRE = T 2 @site1 .ID, T 3 @site1 .SYN = T 3 @site2 .ID In the last step shown in Figure 4, site 1 pushes his changes to site 2 and site 2 pulls these changes from site 1. Because there are no new operations since the authenticator T 3 @site1 was created, no new authenticator is created by site 1. However, the receiving site site 2 has to create a new authenticator since a new operation op 5 is added to the log. T 4 @site2 is therefore computed where:

T 4 @site2 .ID = < site2, {op 5 , op 6 } > (linked to op 5 , op 6 ), T 4 @site2 .SIG = σ site2 (hash(T 3 @site2 .SIG || ∅ || T 3 @site1 .SIG)), T 4 @site2 .IDE = [], T 4 @site2 .PRE = T 3 @site2 .ID, T 4 @site2 .SYN = T 3 @site1 .ID We will discuss in next section the algorithms supporting the creation and verification of logs as well as prove that the proposed algorithms satisfy desired properties which we mentioned at the beginning of this paper.

ALGORITHMS

In this section, we present algorithms to construct authenticators and verify logs based on authenticators. We also provide a proof of correctness of these algorithms.

Authenticators Construction

Algorithm 1 presents the algorithm for the construction of the authenticator when a sender pushes his changes. An authenticator is computed from the its preceding authenticator and the current generated operations. The algorithm takes as argument the log of the sending site S and generates as output the authenticator computed by the sender site. The condition E = ∅ ensures that an authenticator is created only if the sender has generated new changes; otherwise the sender sends the log without computing a new authenticator.

Algorithm 2 presents the algorithm for the construction of the authenticator when a receiver site pulls changes from a sender site. An authenticator is computed from the preceding authenticator of local log, the current operations generated by the receiver and the most recent authenticator of the remote log. The algorithm takes as arguments the two logs of sending site S and receiving site R and it generates as output the authenticator computed by the receiver site. If there are no new operations sent by the sender that have to be added to the log of the receiver, then the receiver will not compute a new authenticator. Note that in synchronizing logs, authenticators that are linked to operations must be also kept in the local workspace as they authenticate previous operations in the log.

Input: sending site S with its log L S Output: T m @S 1 begin 2 E ← list of new operations S generates after T m-1 @S ; T n @R .ID ← <R, T m @S .ID.opID ∪ identifier of most recently local operation at R>;

6

T n @R .SIG ← sign(hash(T n-1 @R .SIG || E || T m @S .SIG));

7

T n @R .IDE ← E; 8 T n @R .PRE ← T n-1 @R .ID;

9

T n @R .SYN ← T m @S .ID; 10 else 11 T n @R ← ; 12 return T n @R ; Algorithm 2: Construct an authenticator for a receiver We will consider time and space complexities of algorithms to construct and verify authenticators. Note that, for the space complexity for verification of authenticators, we exclude the space complexity for maintaining the log. The algorithm to create an authenticator in Algorithms 1 or 2 is O(1) in time, and O(|Δ|) in storage, where Δ is the set of operations whose identifiers are kept in T @site .IDE. Since an authenticator is created each time a site sends or receives changes, the number of authenticators on a replicated object created by site S is the total number of interactions the site has done with other sites. Let Γ be the total number interactions of one site. Then each site needs O(Γ • |Δ| max ) space for all authenticators, where |Δ| max is the maximum Δ of all authenticators. In synchronization, one log is updated to become the union of two logs of sites S and R, and the new log shall need O(Γ S • |Δ S | max + Γ R • |Δ R | max ) space for all authenticators. We can see that the storage complexity depends on the number of interactions and the number of operations generated by two sites.

Authenticators-based Log Verification

The Algorithm 3 presents a mechanism to verify log entries based on authenticators. When a site receives a log of operations accompanied by authenticators, it verifies the log based on these authenticators corresponding to entries in the log. The main idea of verification is to check the authenticity of operations preserved by valid authenticators, including checking:

• If authenticators are valid (their signatures are correct). An authenticator is checked by verifying its digital signature using the public key of signer.

• If the log entries are corresponding to these valid authenticators. When an authenticator passes signature checking, the content and the order of operations are taken into account in the verification.

If all of these checkings pass, the log is authenticated. In contrast, a log with either operations not authenticated or authenticated by invalid authenticators is unauthorized. With any detection of the corrupted data or falsified order of changes, authenticators will be not valid and the verification algorithm returns negative result. Authenticators help users being aware of attacks and once the log is unauthorized, the site which sent tampered log is made accountable for the misbehavior. ). Let us assume one of two sites site 1 or site 2, for instance, site 2 shares the document by sending its log to another site, say site 3. Then site 3 will verify the log it receives from site 2. To verify log, site 3 has to verify the validity of authenticators and log entries. If it already received one part of log before, site 3 can skip checking every authenticator linked to that part. We now describe the worst case when site 3 receives the log from site 2 for the first time and therefore every authenticator needs to be checked. site 3 performs the following steps of the log verification procedure.

Input: site R, log L Output: 1 begin 2 Q ← T n @R ∈ L; // Q: queue of
It starts by checking the most recent authenticator of site 2 T 4 @site2 .

• Verify T 4 @site2 .SIG by using site 2's public key.

• Verify T 4 @site2 .IDE. As T 4 @site2 .IDE = [] then check2 and check3 can be skipped.

• Verify the order of T 4 @site2 .ID (linked to op 5 , op 6 ) and T 4 @site2 .PRE = T 3 @site2 .ID (linked to op 6 ) by checking if the log is maintained correctly (if op 6 is logged before op 5 ). Similarly, the order of T 4 @site2 .ID and T 4 @site2 .SYN = T 3 @site1 .ID (linked to operations op 5 and op 6 ) is checked.

• Since T 4 @site2 was constructed based on T 3 @site2 and T 3 @site1 , these authenticators are put into a queue Q in order to be recursively verified.

If every above check passes then the authenticator T 4 @site2 is said valid. For other authenticators in queue Q, the verification is performed recursively and each verification follows steps in Algorithm 3. The verification finishes when queue Q is empty. The final checking result is only positive if all checks return positive result. Otherwise, the log will be not authenticated. Note that in this example, any deletion or re-ordering of operations is detectable. For instance, if site 2 tries to re-order operations op 2 and op 3 , this attack will be detected by authenticating the authenticator T 2 @site1 which is linked to op 3 . We can see site 2 cannot forge this order on behalf of site 1 since site 1 signed the authenticator linked to op 3 . However, any re-ordering of concurrent operations will not change the verification result. The proof will be presented later.

Authenticators-based log verification has O(1) complexity in space and O(Γ) in time, where Γ is the total number of authenticators in the log. Since authenticators of a log are linked as a hash-chain in which an authenticator is linked to its preceding one, and due to the forward-aggregated authenticity property, it is enough to authenticate the log by checking only the most recent authenticator of a log. This verification process requires checking of all preceding authenticators. Therefore, the time complexity depends on the total number of all authenticators.

Proofs of Correctness

The algorithms, that have been presented previously for authenticators construction and logs verification, ensure the desirable properties for authenticating logs which are linearized from operationbased history. THEOREM 1. A log is tamper-detectable by using authenticators. A misbehaving site cannot selectively insert, delete or change the happened-before order of other sites' operations from the beginning or the middle of the log without being detected by next audit (Integrity).

PROOF. Let M be the misbehaving site who receives a log L = [op 1 , op 2 , . . . , op i , op i+1 , op j-1 , op j ] from site R. Let us assume op i and op i+1 were generated by R and op j-1 and op j were received by R from S. Log L is accompanied with authenticators and the most recent authenticator is T j @R which is linked to operations (op i+1 , op j ). Following Definition 1 and Definition 2, T j @R consists of:

T j @R .ID = <site R, {op i+1 , op j }> (linked to operations op i+1 , op j ), T j @R .SIG = σ siteR (hash(T i @R .SIG || op i || op i+1 || T j @S .SIG)), T j @R .IDE = [op i , op i+1 ], T j @R .PRE = T i @R .ID, T j @R .SYN = T j @S .ID There are three cases that M can attack the log as follows.

• Case 1 -misbehaving site M removes operations at the beginning or in the middle of the log.

(i) If M selectively removes any operation in range from op i to op j from L, i.e. op i is removed by M but M still keeps op i+1 . The authenticator T j @R is then either invalid (missing of op i ) or replaced by T j @R . However, T j @R is invalid since it should be signed by R and M cannot forge R's signature on T j @R .

(ii) If M removes any operation before op i , i.e. op 1 is removed, then the authenticator T i @R is invalid and this makes T j @R invalid consequently.

Therefore, if a misbehaving site removes any operation in the middle of the log, the log will not be authenticated by valid authenticators.

• Case 2 -misbehaving site M changes the happened-before order of operations on behalf of others.

If M changes the happened-before order of any operations from op i to op j then the operations list T j @R .IDE will be invalid. When op i+1 is generated by site R, op j is generated by site S, and R receives op j from S after generating op i , op i+1 , we say op i+1 and op j are concurrent and other users can change the order of op i+1 and op j . In the case of changing order of concurrent operations, the authenticator T j @R is still valid (it passes the check of Algorithm 3 -line 7). However, if R continues to work on the document and adds new operation op k after op j , then commits an authenticator T k @R , other sites cannot change the order of op i , op j and op k since this misbehavior will make the authenticator T k @R invalid by the checking procedure in Algorithm 3 -line 8.

Therefore, if a misbehaving site changes any happened-before order, the log will not be authenticated.

• Case 3 -misbehaving site M inserts an operation at the beginning or into the middle of log.

We assume misbehaving site M inserts an operation op m in the middle of existing log between op i and op j .

If M claims operation op m was generated by site R then the log will be not authenticated since none of existing authenticators of site R authenticates op m and it therefore cannot pass the verification process in Algorithm 3 -line 17, 18.

If M claims op m was generated by himself, then it needs to commit an authenticator to authenticate op m . In such case, op m is considered concurrent with other operations, so it can be inserted into any position in the log L and L is still authenticated.

Therefore, a misbehaving site only can insert its own operations into its local log. The site cannot claim its insertion as operations on behalf of others because it cannot authenticate such operations.

In summary, it is impossible to forge the integrity of a log without being detected by using authenticators. THEOREM 2. Authenticators preserve concurrency-collisionfreeness property.

PROOF. In the proof of theorem 1, we use a log L of site R, L R = [op 1 , op 2 , . . . , op i , op i+1 , op j-1 , op j ]. We assume operations op i , op i+1 are concurrent with op j-1 , op j . Thus the order between them can be interchangeable in any linearization of history. Let us consider that site S maintains a different log of same history L S = [op 1 , op 2 , . . . , op j-1 , op j , op i , op i+1 ]. We will prove that the log verification will return the same result on checking L S and L R .

When sites S and R share logs with each other, we suppose that T i @R and T j @R are committed by site R before and after receiving the log from site S; T j @S and T i @S are committed by site S before and after receiving log from site R. The log verification by checking T i @S and T j @R yields the same result regardless the order of concurrent operations. Indeed, T i @S and T j @R are valid only if they pass four checks (Algorithm 3, line 6 -9). Consider check1 and check2 were passed, therefore they must pass check3 and check4 to be completely verified. The check3 only deals with the order of preceding authenticator against operations list IDE (T i @S with op i , op i+1 , T j @R with op j-1 , op j ) and these orders are preserved as proved in Theorem 1. The check4 deals with the orders of preceding and synchronized authenticators with respect to the committed authenticator. Since T j @R is committed after T i @R and T j @S (linked to operations op i+1 , op j ), the check4 for T j @R passes. Similarly, the check4 for T i @S passes. Therefore, regardless the logging order of concurrent operations, the verification yields same result of checking two logs L S and L R . THEOREM 3. Authenticators are forward-aggregated.

PROOF. This property is achieved by using hash-chain based authenticator, so that T i @site .SIG includes T i-1 @site .SIG in its construction. THEOREM 4. Every site which is in possession of history can verify authenticators by using the public key of the site which committed them. A site which created an authenticator cannot deny having constructed it (public verifiability).

PROOF. Non-repudiation is an important feature of digital signatures. By this property, a site that has signed authenticators cannot at a later time deny having signed them. Suppose that site S has signed an authenticator for operations op 1 , op 2 , ..., op i and shared them with another site. At later time, site S wants to change the history by removing op i (e.g insert line X). In that case, site S should add a new operation op j (e.g delete line X) instead of removing operation op i since this will make authenticator T i @S invalid. Once a log has been shared with other sites, site S cannot remove its operations due to the using of non-repudiation signature for committed authenticators. Authenticators are linked to operations and replicated together with logs, therefore anyone can authenticate them.

EVALUATION

We are going to present a practical evaluation of our proposed algorithms to authenticate logs. As the time complexity for the creation of authenticators is not significant, we evaluated the time complexity of the algorithm for log verification based on authenticators. Verification is done when a site clones or pulls remote log and it needs to check if the remote log is shared correctly without any tampering.

We carried out experiments on real logs from projects that used Mercurial as a distributed tool for source code management. We chose randomly two projects: Hgview project [22] and one branch of OpenJDK project [START_REF]OpenJDK[END_REF]. The project Hgview includes almost 700 committed patches stored in repository gathering contributions from 20 developers with 115 interactions between them. One branch of OpenJDK stored about 350 committed patches in repository which were created by 31 developers with 253 interactions between them. A committed patch is a sequence of operations that a user commits. It is also called a log entry. We implemented our experiments by using Python programming language.

In the histories of projects developed with Mercurial or any other distributed version control system, we are unable to know when a user pulls changes. We can only have information about push operations. We therefore considered the worst case scenario where a pull is performed at each new entry in the repository by an arbitrary user Y that had never interacted before with any other user X that contributed to the project. If previous interactions were taking place between users Y and X, an optimization could be applied. In the experiment, we have first traversed the repository to extract entries and user names who contributed to the project. Then we generated for each user one RSA key pair which is later used to sign authenticators. Authenticators are created based on linearized logs of repositories. Finally, verification time is measured for the worst case scenario where a newcomer clones the repository and she has to check all authenticators created by previous contributors. The results are computed by the average values of five run times. Figure 5 presents the experimental results for the worst case behavior. In two experiments with the input data from Hgview project and OpenJDK project, the checking time grows linearly with the increasing number of authenticators. It is observed that it takes less than 50 milliseconds (ms) to verify a log if its size is less than 100 entries (this size is common for the size of all files observed in these projects). However, to check the whole repository, the verifying time depends mostly on the number of interactions between users (this means also the number of authenticators). In Figure 5, we notice that the runtime to verify log of the Hgview project is less than that of OpenJDK project even though its log size is bigger.

The main conclusion to be drawn from the results is that adding authenticators to secure logs does not create a significant time overhead for collaborative systems even for the worst case. Sites can reduce the time to verify log by skipping authenticators which are already checked when previous pulls were performed.

RELATED WORK

In this section, we give a review of existing securing log schemes and highlight their non suitability for securing operation-based history in multi-synchronous collaboration.

Several works introduce a trusted server to be used for verification. This approach makes the system open to a single point of failure. Peterson et al. [START_REF] Peterson | Design and implementation of verifiable audit trails for a versioning file system[END_REF] presents an approach to secure version history in a versioning file system. The approach proposed a design of a system based on generating message authentication codes MACs for versions and archiving them with a third party. A file system commits to a version history when it presents a MAC to the third party and at a later time, an auditor can verify this history. Thus it requires that the system trusts the third party that maintains MACs correctly. In the general model of multi-synchronous collaboration, users have no need to rely on a trusted third party and therefore any user should be able to verify logs.

In a similar direction, Haeberlen et al. designed PeerReview [START_REF] Haeberlen | Peerreview: practical accountability for distributed systems[END_REF] to provide accountability and fault detection for distributed systems. It guarantees the eventual detection of all Byzantine faults. Peer-Review framework contains tamper-evident logs and commitment, consistency and audit protocols. However, each node should have an identical log with others. It does not support that each node can keep different orders of operations as in operation-based multisynchronous collaboration where users maintain different streams of activity on the shared data. The framework offers three applications of overlay multicast, network file system and peer-to-peer email, however, all of these applications do not deal with parallel modifications of data that is the case in multi-synchronous collaboration.

The integrity of audit logs has traditionally been protected through the use of one-way hash functions. There is a line of work that addresses the forward-secure stream integrity for audit logs. Ma et al. proposed a set of secure audit logging schemes and aggregate signatures [START_REF] Ma | Extended abstract: Forward-secure sequential aggregate authentication[END_REF][START_REF] Ma | Practical forward secure sequential aggregate signatures[END_REF][START_REF] Ma | A new approach to secure logging[END_REF]. Forward security ensures the integrity of log entries in the log stream and no selective deletion or re-ordering to stream is possible. Recently, Yavuz et al. proposed their work to secure audit log such as BAF [START_REF] Yavuz | Baf: An efficient publicly verifiable secure audit logging scheme for distributed systems[END_REF] that was developed to achieve at the same time the computationally efficient log signing and the truncation-attack-resistant logging. This work could be applied only for a particular case of the multi-synchronous collaboration where all users maintain the same linearization of the collaboration history. However, it cannot be applied for the general case of the multisynchronous collaboration where users work on different streams of activity on the shared data corresponding to different linearizations of collaboration history.

There is another line of work that relies on authenticated data structures to secure logs in distributed systems [START_REF] Goodrich | Implementation of an authenticated dictionary with skip lists and commutative hashing[END_REF][START_REF] Maniatis | Authenticated append-only skip lists[END_REF][START_REF] Maniatis | Secure history preservation through timeline entanglement[END_REF][START_REF] Papamanthou | Authenticated hash tables[END_REF]. While these approaches are computationally efficient, they do not deal with history for collaboration. Maniatis et al. introduced Timeweave [START_REF] Maniatis | Secure history preservation through timeline entanglement[END_REF] that uses a time entanglement mechanism to preserve the history state of distributed systems in a tamper-evident manner. However, Timeweave does not handle the information flows synchronized which is required in optimistic replication where concurrent operations appear in different orders in replicas.

Apart from above approaches, there are works that address securing logs for replication systems. Spreitzer et al. [START_REF] Spreitzer | Dealing with server corruption in weakly consistent, replicated data systems[END_REF] uses hash chain to protect modification orders of a weakly consistent, replicated data system. Kang et al. [START_REF] Kang | The hash history approach for reconciling mutual inconsistency[END_REF][START_REF] Kang | S2D2: A Framework for Scalable and Secure Optimistic Replication[END_REF] proposed SHH for optimistic replication using hash values as in Merkle tree [START_REF] Merkle | Secrecy, authentication, and public key systems[END_REF] for revision identifiers to protect causality of version history. It serves mainly for the purpose of securing version history construction when the log was pruned in limited storage environments such as mobile computing; and for checking distributed replicas' convergence. By ensuring decentralized ordering correctness, SHH can guarantee that all updates are not vulnerable to a decentralized ordering attack. However, SHH cannot ensure the integrity of data in the sense that it is original or forged. Using SHH the sender signature cannot be included in summary hashes since that makes them different even if the merged versions are identical, thus it makes replicas diverge. Without digital signature in summary hashes, SHH cannot protect history from attacks of unauthorized actions and it cannot provide authenticity and accountability. Similar approaches to SHH in which hashes are used as identifiers are implemented in distributed version control systems such as Git history [START_REF] Loeliger | Collaborating with Git[END_REF] and Mercurial history [START_REF] O'sullivan | Mercurial: The Definitive Guide[END_REF].

Concerning securing document history, Hasan et al. [START_REF] Hasan | The case of the fake picasso: Preventing history forgery with secure provenance[END_REF] proposed a mechanism of preventing history forgery for a document history where a document refers to a file or database. In [START_REF] Hasan | The case of the fake picasso: Preventing history forgery with secure provenance[END_REF], the term "provenance" is used for the history of the ownership of items and actions performed on them. The authors present a provenance-aware system prototype that captures history of document writes at the application layer. To prevent all potential attacks on provenance chain, it requires trusted pervasive hardware infrastructure at the level where tracking is performed. However, contributions to the shared document/database are done sequentially and the approach does not deal with merging of parallel contributions to the shared document.

A different work, Mella et al. [START_REF] Mella | Controlled and cooperative updates of xml documents in byzantine and failure-prone distributed systems[END_REF] proposed a framework to the document control flow in a highly distributed environment. The proposal is aimed at cooperative updates on a document flow with delegation and security policies. However, it considers one stream of update process rather than a multi-way flow of updating with reconciliation as in multi-synchronous model. Moreover, security access control policies are defined at document's attributes level that means each document atomic element is marked with a label containing a set of access control policies that apply to it. The approach described in [START_REF] Mella | Controlled and cooperative updates of xml documents in byzantine and failure-prone distributed systems[END_REF] secures different XML elements, while we aim to secure patches of operations.

In the domain of database security, Mahajan et al. [START_REF] Mahajan | Depot: Cloud storage with minimal trust[END_REF] proposed Depot to secure replicated database in the cloud. Among all issues addressed in Depot, we focus on the issues of consistency, integrity and authorization. Depot addresses these issues in the context of database where data is stored in the form of key/value and update is the main operation performed over database. We consider collaborative systems with more operations beyond update, i.e. insert, delete content to/from the shared document. Depot ensures consistency by using version vectors and version history hashes. Each update is signed by authorized node to enforce consistency and integrity. This would be too costly in a collaborative working environment where users produce a huge number of operations on the shared document. Our approach secures logs without requiring that each user signs each operation. Authenticators are created for a patch of operations each time the log is pushed/pulled to/from one user.

The state of the art of secure audit logging research was also surveyed by Accorsi [START_REF] Accorsi | Safe-keeping digital evidence with secure logging protocols: State of the art and challenges[END_REF]. Though secure audit logging was intensively investigated, we are not aware of any work that ensures secure audit logs for a collaboration history with partial order where users maintain different total ordered logs of the collaboration history corresponding to their activity streams.

CONCLUSION

In this paper, we introduced a technique using authenticators to face security challenges in operation-based multi-synchronous collaboration. In multi-synchronous model, users work simultaneously on different streams of activity. As the collaboration progresses, the streams of activity continually diverge and synchronize. Authenticators are used to ensure integrity and authenticity of logs of operations corresponding to different streams of activity during a collaborative process. While tamper-resistance is impossible to be ensured in multi-synchronous collaboration without a central provider, tamper-detection should be guaranteed. We presented an approach for securing logs that made misbehaving users accountable in collaborative systems without the need of a central authority. We provided proofs of correctness of our approach and analyze the complexities of our algorithms. We also conducted a set of experiments testing our proposed approach on real histories of collaboration extracted from real projects using Mercurial. The results show the feasibility of our approach that can be used to provide security, trustworthiness and accountability to distributed collaborative systems.

Figure 1 :

 1 Figure 1: Push-Pull-Clone paradigm

5 Figure 2 :

 52 Figure 2: History and its linear extensions

Figure 3 :

 3 Figure 3: Structure of an authenticator.

2 Figure 4 :

 24 Figure 4: Example of constructing authenticators.

3 if E = ∅ then 4 T 2 E 3 E

 3423 m @S .ID ← <S, identifier of most recently local operation at S>; 5 T m @S .SIG ← sign(hash(T m-1 @S .SIG || E));6 T m @S .IDE ← E; 7 T m @S .PRE ← T m-1 @S .ID; 8 T m @S .SYN ← ∅ ;9 else 10 T m @S ← ; 11 return T m @S ; Algorithm 1: Construct an authenticator for a sender Input: sending site S, receiving site R and their logs L S , L R Output: T n @R 1 begin ← list of new operations R generates after T n-1 @R ; S ← list of new operations from L S added to L R ; 4 if E S = ∅ then 5

authenticators to verify 3 verified ← True; 4 while Q = ∅ do 5 TAlgorithm 3 :

 3453 ← Q.get(); 6 check1 ← T.SIG is correct; 7 check2 ← order of operations in L corresponds to T.IDE list; 8 check3 ← T.PRE precedes operations in T.IDE; 9 check4 ← T.PRE and T.SYN precede T.ID; 10 if check1 & check2 & check3 & check4 then 11 mark operations in T.IDE as checked; 12 put(Q, T.PRE); 13 put(Q, T.SYN); Verify a log Let us revisit the example in the previous section (see Figure.

4

 4

Figure 5 :

 5 Figure 5: Time overhead to check authenticators created for Hgview and OpenJDK repositories.

Acknowledgment

This work is partially funded by the ANR national research grant STREAMS (ANR-10-SEGI-010).


Hien Thi

Thu Truong

Claudia-Lavinia Ignat

Pascal Molli
email: pascal.molli@acm.org

Securing Logs in Operation-based Collaborative Editing

Keywords: secure log, authenticator, auditing, operation based optimistic replication ACM Classification C.2.4 Computer-Communication Networks: Distributed Systems [Distributed applications], D.4.6 Operating Systems: Security and Protection [Authentication, Information Flow Controls], K.6.5 Management of Computing

In recent years collaborative editing systems such as wikis, GoogleDocs and version control systems became very popular. In order to improve reliability, fault-tolerance and availability shared data is replicated in these systems. User misbehaviors can make the system inconsistent or bring corrupted updates to replicated data. Solutions to secure data history of state-based replication exist, however they are hardly applied to operation-based replication. In this paper we propose an approach to secure log in operation-based optimistic replication system. authenticators based on hash values and digital signatures are generated each time a site shares or receives new updates on replicas. authenticators secure logs with security properties of integrity and authenticity. We present in detail algorithms to construct and verify authenticators and we analyse their complexities.

INTRODUCTION

Collaboration is a key requirement of teams of individuals working together towards some common goal. In recent years collaborative editing systems such as wikis, GoogleDocs and version control systems became very popular. In order to improve reliability, fault-tolerance and availability, shared data is replicated in these systems. As shared data is mutable, consistency among the different replicas must be ensured. Rather than adopting a pessimistic replication mechanism that blocks Optimistic replication can be classified into state-based and operation-based [START_REF] Lippe | Operation-based merging[END_REF]. In state-based replication each site applies updates to its replica without maintaining a change log. Usually in systems adopting a state-based replication, every site sends its local state to other replicas that can merge the received state with their own state. Systems that use operation-based replication keep modifications performed on the replica in a log which is then sent to the other replicas. Operation-based approaches are used when cost to transfer state is high such as databases, mobile systems and when operation-semantics is important. In this work we target systems that use operation-based replication.

However, in operation-based replication systems users can misbehave and propagate incorrect contents to other users such as falsifying the causal order of the operations or removing some contents which are not allowed to be removed. Some mechanisms for securing operation-based logs exist [START_REF] Ma | A new approach to secure logging[END_REF][START_REF] Hasan | The case of the fake picasso: Preventing history forgery with secure provenance[END_REF], but they are not adapted for optimistic replication where concurrent modifications can be done in parallel on the replicas. A mechanism for securing changes in optimistic replication was proposed in [START_REF] Kang | The hash history approach for reconciling mutual inconsistency[END_REF], but it is applicable only for statebased replication.

In the domain of data security, security properties [START_REF] Menezes | Handbook of Applied Cryptography[END_REF] are defined including confidentiality, integrity, authenticity, access control, availability. For the purpose of preventing log tampering, in this paper we consider two of these security properties: integrity and authenticity. We informally consider such security properties as follows:

• Integrity. Adversaries cannot forge an event of document such as modify content or introduce new forged events to document log without being detected. Integrity is the most important required property for securing operation-based replication. Securing the individual document can be done by using cryptographic signatures or checksums. However, ensuring the integrity of a replicated document represented by a log of operations is more difficult as operations cross multi-contributors and some of them might be adversaries.

• Authenticity. Any user in a system can verify the validity of events in a log. Adversaries are made accountable for unauthorized actions. This property can be done by using non-repudiation digital signatures such as RSA or DSA.

Traditionally, hashes are used to ensure integrity of any data object. However, in replication systems this data object changes due to the contributions of distributed users. Thus a tamper-evident update history is maintained to mitigate security challenges. Such histories containing record information of the updates that have been performed on the replicas along with the causal orderings of these updates are constructed in the manner that any tampering to previous version of replicas will be detected at other replica sites.

In this paper, we present scenarios that expose vulnerabilities of operation-based replication and then present an approach named to create authenticators that prevent users from tampering logs. authenticators detect if original data was modified or operations were reordered. Our solution ensures the integrity of shared documents in an operation-based replication system and the authenticity of user changes.

The structure of the paper is organized as follows. Section summaries related work in the domain of securing logs in distributed systems. Section introduces operation-based optimistic replication and conceptual operation-based model. Section presents algorithms to secure logs by authenticators along with their construction and verification. And Section concludes the paper.

RELATED WORK

Logging systems and audit logs are very useful and widely used in distributed systems, however existing approaches with log auditing and authenticator do not work for replication systems, particular for operation-based replication. Among these approaches, Peterson et al. presents an approach to secure version history in a versioning file system [START_REF] Peterson | Design and implementation of verifiable audit trails for a versioning file system[END_REF]. The approach proposed a design of a system based on generating message authentication codes (MACs) for versions and archiving them with a third party. A file system commits to a version history when it presents a MAC to the third party and at a later time, an auditor can verify this history. Thus it requires that the system trusts the third party that maintains MACs correctly. In our system we do not rely on a third party and any user can perform a log auditing mechanism.

Secure audit logs based on hash chains and signatures have been widely used. Most of existing proposals are not suitable to apply directly to operation-based replication. Kang et al.

proposed SHH [START_REF] Kang | The hash history approach for reconciling mutual inconsistency[END_REF] for optimistic replication using hash values in Merkle tree as revision identifiers to protect causality of version history. By ensuring decentralized ordering correctness, SHH can guarantee that all updates are not vulnerable to a decentralized ordering attack. However SHH cannot ensure the integrity of data contents to verify update is good or forged. The sender signature can not be included in generating summary hash since that makes summary hashes different even if the merged versions are identical, thus it makes replicas divergence. Thus it cannot provide the authenticity property. Similar approaches to SHH in which hashes are used as identifiers are implemented in distributed version control systems such as Git history [START_REF] Loeliger | Collaborating with Git[END_REF] and Mercurial history [START_REF] O'sullivan | Mercurial: The Definitive Guide[END_REF].

In other related works such as secure provenance [START_REF] Hasan | The case of the fake picasso: Preventing history forgery with secure provenance[END_REF], secure timeline [START_REF] Maniatis | Secure history preservation through timeline entanglement[END_REF], secure logging [START_REF] Ma | A new approach to secure logging[END_REF], secure cooperative XML updates [START_REF] Mella | Controlled and cooperative updates of xml documents in byzantine and failure-prone distributed systems[END_REF], the proposals address problem of handling information flow in highly distributed manner. However they only consider one-path of updating process rather than multi-paths with reconciliation as in collaborative editing.

OPERATION-BASED REPLICATION

In this section, we first start by presenting operation-based model in the context of our system. Then we will look into the vulnerabilities that could arise in replicated phases of a shared object.

System model

We consider a system of N sites of users which can operate independently on replicas. Each site keeps a document (replicated object) as a log of operations that have been performed during collaborative process. An object can be as large as a database (i.e. Bayou) or as small as a single file (i.e. WinFS file). An object is created at one site and propagated to other sites which contain a replica of the object. A site may replicate an object to any other sites. When a site which keeping a replica receives the updates, a process called replica synchronization will be performed. During synchronization, it requires to detect the concurrency and causality between updates of different sites. Also, it requires to resolve conflict if it occurs between concurrent updates. Replicas are consistent if their states are identical when they have the same set of operations. Two replicas are consistent after synchronization if each replica is maintained correctly. To ensure this we use authenticator after each sharing of replicated object. Operation-based replication maintains a history of operations and with operation transfer, only missing operations are sent to bring other replicas up-to-date (i.e. anti-entropy propagation with minimal traffic overhead). Receiving replicas updates new operations to their logs. From the log it is possible to see what are user contributions to different parts of the document and when these contributions were generated. Two users can make progress independently on the shared document. The changes are propagated in weakly consistent manner. It means user can decide when, with whom and what data to be sent and synchronized.

Definition 1. An operation-based replicated object in a system of N sites is a log of operations which were performed to transfer a document D from an initial version V 0 to a final version V k . Operations can be seen in different granularity, such as, lines or paragraphs in document, or deltas between revisions. Each operation recorded in the log is called an event. A shared object is considered as a log of events L = [e 1 , e 2 , ..., e k ]. Each event is parameterised by systems or applications.

In the operation-based replication system, the input of synchronization is a common initial state and logs of operations that were performed on each replica. The system merges the logs in some fashion, and replays the operations in the merged log against the initial state to yield a reconciled version. Logs provide the history of site operations which can help to infer information about user's intents and therefore potentially more powerful.

For instance, in Fig. 1 each site has an initial version V 0 . At a later time, sites create or synchronize new updates on each single replica to create new versions as logs of operations by manipulating with lines or paragraph of the document such as

V 1 = [op 1 , op 2 ], V 2 = [op 1 , op 3 , op 4 ], V 3 = [op 1 , op 2 , op 5 ], V 4 = [op 1 , op 2 , op 5 , op 3 , op 4 ], V 5 = [op 1 , op 2 , op 5 , op 4 , op 3 ] .
Users store operations in their logs in an order that is consistent with generation order. The collaboration of users involves logs reconciliation. When a user u receives a remote log L from a remote user v through anti-entropy propagation [START_REF] Demers | Epidemic Algorithms for Replicated Database Maintenance[END_REF], u elects new events from L to append to his log L. Log synchronization of any two replicas ensures duplicate elimination.

Causality and Concurrency

As users perform updates locally, replicas diverge from one another. Operations isolated on one site are propagated to other sites and are integrated or replayed there to make sites convergent. Since the log is an operation-based replicated it is possible to replay operations to get a state-based document.

In order to guarantee convergence, it requires techniques to maintain and execute operations in correct orders, such as enforcing total order of operations before execution or using operational transformation, or using commutative replicated data type (CRDT) such as Logoot [START_REF] Weiss | Logoot-Undo: Distributed Collaborative Editing System on P2P Networks[END_REF] in which concurrent operations can be replayed in variant orders. Note that as concurrency can occur in the replication, the orders of concurrent operations might vary in logs. Thus authenticators are designed to protect causality while allow variant orders of concurrent operations.

Reconciliation

A sequence of events either isolated or reconciled from other users are added to the log. We assume reconciliation process modifies one log so that it becomes the union of the two logs by adding new operations to the end of the log with respect the order as in original logs. As we mentioned previously that replica diffusion uses anti-entropy mechanism which preserves causality orders of operations and the reconciliation ensures causality of operations as well as allows that concurrent operations appear in logs in variant orders.

When a sending site sends a document to a receiving site, it creates an authenticator for its log to attach with the sent document. The receiving site creates a new authenticator when it receives the document. We assume each site involved in the update process possesses a cryptographic public key pair that is corresponded to a unique site identifier and that all the other users can retrieve the public key of each other.

This assumption is reasonable in practice [START_REF] Walsh | Experience with an Object Reputation System for Peer-to-Peer Filesharing (Awarded Best Paper)[END_REF][START_REF] Mella | Controlled and cooperative updates of xml documents in byzantine and failure-prone distributed systems[END_REF]. The key pair is used to sign entries of log that prevent malicious sites modifying events on behalf of other users. Though sites can choose a public key pair on their-own, to limit Sybil attacks [START_REF] Douceur | The sybil attack[END_REF] we can require each site possesses a digital certificate from trusted certification authority or have an offline channel (such as email) to identified the owner of public keys. In either case the certification authority plays no role in creating authenticator process, and it is used only during initial phrase when a site joins the system. We also use cryptographic hash function H with properties collision-and preimage-resistant.

The collision-resistant property can be used to establish the uniqueness of logs at a certain moment when an authenticator is created.

Vulnerabilities to document

In optimistic replication, the correctness of document history is based on the trustworthiness of users who maintain its own ordering of versions correctly such as when a user generates new updates, the order of new version should follow all previous versions. Unfortunately a malicious user can always generate phony updates to forge the history or alter the order of versions. This attacks make the document inconsistent among replicas. Users can update corrupted data from malicious site and discard data from valid site. Replicas with corrupted update might never converge with other valid replicas while victim site whose updates were lost and this is really problematic in replication system. In Fig. 1 we present an example of a malicious site that generates phony updates without being detected. There are two types of malicious users that are insider and outsider. We consider in this paper an inside adversary who has full rights to access to replicated object. Such an adversary might want to alter the process including actions performed on data of authorized contributors. For example when Alice provides a document to Bob who can perform and contribute new updates to the document, he should not be able to modify history of actions that Alice performed which were recorded in document log. The main goals of an adversary include: alerting existing records or adding forged information to logs (this might include involve forging other individual events, changing the order of events, or adding forged events into the log).

V 0 V 0 V 0 op 1 op 1 op 1 V 1 op 1 op 2 V
Our work assumes only adversaries who act inside of a system since we cannot stop an adversary from copying data to create a new document and claim at a later time as owner. It might be possible if an adversary remove completely the log of operations, however in such case it means the document will be removed. We can deal with other types adversary (insider or outsider) with the support of trusted platform or system; however we do not consider this assumption in our system model.

The replication-based collaboration the secure of data items during the document collaborative workflows has gained increasing importance. As an example, if Bob receives a document and processes a part thereof and then forward to Claude, the operation-based document should include the chronology of actions that each user (Alice, Bob, Claude) performed on the document.

AUTHENTICATOR

In this section we are going to present our approach to create authenticator A in details which can ensure integrity and authenticity and suffer Byzantine attacks for operation-based optimistic replication.

Authenticator

In our context, we define authenticator as follow:

Definition 2. An authenticator is a log tamper-evident denoted as A which captures a sub sequence of one or more events (operations) of the log in one updating session to protect their integrity and authenticity; where an updating session at one user's site is considered as a duration before the user sends or receives subsequent updates to/from other users.

For illustration this definition, let consider at a site of user u at certain writing session the log is [e 1 , e 2 , e 3 , e 4 , e 5 ]. The user u creates an authenticator A for these events with willingness that when the log is synchronized at other replicas, it cannot be tampered by receiver, for example, the receiver reorders e 1 and e 2 to change the causal-dependency of e 1 and e 2 .

Definition 3. Each authenticator A as a tuple ID, SIG, POS, IDE, PRE, SYN holds:

• ID: identifier of authenticator including site identifiers U (and V ) who commits (and receives) the authenticator and an event identifier that the authenticator is linked to;

• SIG: the value (signature signed by a public key PK of a user U to verify the authenticator later) of a certain state of document D based on operations;

• IDE: a list of identifiers of events which are used in the SIG;

• PRE, SYN: identifiers of preceding and receiving authenticators used to compute value of the authenticator; Definition 4. The SIG of an authenticator A at a certain update is computed as a signature of a cumulative hash by a sender S or a receiver R, where the sender computes SIG of the latest authenticator A S n .SIG = σ S {H(A S n-1 || E)} with a condition that E = ∅; and the receiver computes When a user shares a document by sending the whole log, he creates an authenticator for log events computed based on preceding authenticator, new updated events. The authenticator is signed by his private key and linked to the last event of the log. At the receiving site, the receiver performs reconciliation and creates a new authenticator up on reception.

A R m = σ R {H(A R m-1 || E ||A S n )} with a condition that A R m-1 = ∅ or A S n = ∅ or E = ∅;
The authenticators of a log of operations are constructed whenever a site sends or receives a new update to/from another site. An authenticator is created in following cases:

• A site sends new updates to other sites. In this case, if a site sends a document without new updates, no new authenticator is created.

• A site receives new updates from other sites. In this case, the receiving site will check the remote log, detect and resolve conflicts (if there are some conflicts of operations). After these actions, if there are new updates that are added to the receiver's log, new authenticator is created for these new updates.

As an example, we consider three sites A, B and C who collaboratively work through a shared object as a document with the initial version V 0 /{op 1 }. Each site performs isolated updates on the initial version to contribute to the object. In detail, site A, B create new versions V 1 /{op 1 , op 2 } and V 2 /{op 1 , op 3 , op 4 } independently. At a later time site A reconciles with updates from site B to achieve new version V 4 /{op 1 , op 2 , op 5 , op 3 , op 4 }.

Fig. 1 shows one of vulnerabilities to forge versions. In this scenario, site A changes the content of reconciled version V 4 to forged version V ′ 4 for her purpose. Later when site A shares the forged version V ′ 4 to site C, site C cannot know this version contains corrupted data that site A performed on the updates of site B. Also if site C then receives version V 2 from site B, site C cannot know which version either V 2 or V ′ 4 contains correct content.

Our proposal with authenticators is one solution to avoid this forge. When user B shares his replica first time with user A, he creates an authenticator A B 1 . As definition 4 to compute authenticator for a sender, A B 1 is computed with 1 . Later on, C receives the document from B but since no events are new to C no new authenticator is created. Now we discuss that the authenticators created on this example can guarantee the integrity and authenticity of replicas. Let consider the case site A wants to forge version V 4 which is reconciled from V 2 and V 3 . Since site A receives op 3 and op 4 from site B with authenticator A B 1 , and then A changes the order of op 3 and op 4 , this tampering will be detected by C when A sends the forged version to C. Authenticator A B 1 guarantees that A cannot forge operations on behalf of B. Similarly authenticator A A 1 guarantees that C cannot forge operations on behalf of A.

A B 1 .SIG = σ P K B {H(op 1 ||op 3 ||op 4 )}.

Algorithms

We present in details algorithms to create and verify authenticators in the following subsections.

Constructing authenticator

Since an authenticator is computed from preceding authenticator of the log, the current events and the authenticator of synchronized log, the input data to compute authenticator are two logs at site U and V, two sets of authenticators Z U and Z V . If it is the first authenticator, one of these parameters can be empty. In Algorithm 1, if L' = ∅ then there is no remote log to synchronize and it is the case when a sender computes an authenticator before sending his updates. The condition E = ∅ ensures that an authenticator is created only if the sender has generated new updates; otherwise the sender sends the log without computing any new authenticator.

Note that when synchronizing replicas, their authenticators that are linked to operations must be also synchronized so that all events from remote replica are authenticated when they are appended to other replicas.

For the complexity analysis, we assume the size of logs L and L ′ are treated as constants. We consider time and space complexities of A in algorithms of constructing authenticator and verifying authenticator.

An authenticator construction in Algo.1 is O(1) in time, and O(|∆|) in storage, where ∆ is the maximum number of events that are linked to A.IDE to keep a list of events. Since authenticator is created each time a site sends or receives (so-called interaction) updates, the number of authen-

Input:

A log L of site U and an authenticator set Z U ; A log L' of a site V and an authenticator set Z V ; The last authenticator of L: A U n-1 ; The last authenticator of L': A V m ; Output: new authenticator created by U: A U n begin 1 E ← [e i 1 , ..., e ir ] as new events added by U to L from last A U n-1 ;

2 if L ′ = ∅ then 3 if E = ∅ then 4 A U n .ID ← U,
Z U ← Z U ∪ Z V ; 21 Add(Z U , A U n );
| + Θ • |∆ V |)
space, where ∆ U and ∆ V are maximum number of events authenticated in any authenticator of U and V. We can see the storage complexity depends on the number of interactions and the number of events between two interactions.

Auditing authenticator

The algorithm algo. 2 presents a mechanism to verify authenticators. When a user receives a document as a log of operations together with authenticators, he verifies these authenticators against to events in the log. The main idea of the verification is to check the authenticity of events with valid authenticators. Thus a log with either events are not authenticated or they are authenticated by invalid authenticators is unauthorized. An authenticator is checked by verifying its digital signature. In the verification not only the content but also the order of events are taken into account. If the corrupted data or falsified order of updates were introduced, authenticators will not be valid corresponding to the events and the verification algorithm returns negative result. Authenticators help to aware attacks and once the log is detected as unauthorized, the user who sent the log is made accountable for the misbehavior.

Authenticator verification has O(1) complexity in space and

O(Γ) in time,
where Γ is the total number of authenticators in the log of replica. Since authenticators in a log are linked as a chain in which an authenticator is linked to a preceding one, it is enough to authenticate the log by checking the last authenticator in a log. This checking process requires to pass through all preceding authenticators, and that makes the time complexity depends on the total number of all authenticators.

CONCLUSION

In this paper we addressed security challenges in operationbased optimistic replication systems. To ensure integrity and authenticity of logs of operations during collaborative process, authenticators are computed and attached to logs as replicated objects. We argue that authenticators work for operation-based replication systems while existing approaches cannot be directly applied to such systems. While tamper-resistance is impossible to be ensured in replication systems, tamper-detection should be guaranteed. We presented an approach for securing logs that made misbehaving users accountable in a peer-to-peer environment where there is no central authority. We plan to apply our approach on real traces of collaboration such as on available projects developed using Mercurial and measure the complexity of our approach in this case.

1 .

 1 An the authenticator is described fully as A B 1 = ID:{B, 1}, A B 1 .SIG, POS:op 4 , IDE:op 1 , op 3 , op 4 , PRE:∅, SYN:∅ . When user A receives updates from user B, she performs synchronization and updates only new operations to the log, and creates an authenticator for new version of document, A A 1 where A A 1 .SIG = σ P K B {H(op 1 || op 2 op 5 || A B 1 )}, and A A 1 = ID:{A, 1}, A A 1 .SIG, POS:op 4 , IDE:op 1 , op 2 , op 5 , PRE:∅, SYN:A B These authenticators are linked to event op 4 . When C receives the document from A, he updates new changes to his replica and creates a new authenticator A C

  Authenticator construction ticators on a replicated object created by a site u is the total number of interactions the site performed during the development process of the object. Let |Γ| be the total number interactions of one site, each site needs O(Γ • |∆|) space. In synchronization, one log is updated to become the union of two logs, and the new log shall result with O(Γ • |∆ U

  However replicas might not converge if they execute operations in different orders. As the Lamport definition of causality, two operations op a and op b generated at sites i and j are in causal dependency op a → op b if: op a happened before op b and i = j; or the execution of op a at site j happened before the generation of op b . Otherwise they are concurrent (op a || op b ), that means neither op a → op b nor op b → op a .

  : the last m th authenticator committed by receiver; • E = [e i1 || e i2 || ... e ir ]: subsequent updates generated after preceding authenticator;

	where,
	• A S n : the last n th authenticator committed by sender;
	• A R

m • (σ u {H(⊙|| . . . ||⊙)} denotes the concatenated arguments are hashed and signed with user u's private key).

  e ir ;

	5
	6	A U n .SIG ← σu{H(A U n-1 ||e i 1 ||...||e ir )};
	7	A B n .IDE ← e i 1 , ..., e ir ;
	8	A B n .PRE ← A U n-1 .ID;
	9	A B n .SYN ← ∅;
	10	end if
	11	end if
	12	else
	13	if A U n-1 = ∅ or A V m = ∅ or E = ∅ then
	14	A U n .ID ← U, e ir ;
		A U n .SIG ← σu{H(A U n-1 ||e i 1 ||...||e ir ||A V m )};
	16
	17	A B n .PRE ← A U n-1 .ID;
	18	A B n .SYN ← A V m .ID;
	19	end if
	20	end if

15 A B n .IDE ← e i 1 , ..., e ir ;

  Let Q be a queue storing authenticators to be verified; Extract ID, U, PK, SIG, POS, IDE, PRE, SYN from A;Marked events in L with identifiers ∈ IDE;

		Input:
		A log L of site U;
		A list of authenticators AL U ;
		Output:
		A boolean result AUTH, misbehaving site M (if found)
	1	begin
	7
	8	Verify SIG by public key PK on signed data of
		H(PRE||IDE||SYN) ;
	9	if order/content of events in IDE and order of PRE,IDE valid then
	10
	11	Add(Q, PRE);
	12	Add(Q, SYN);
	13	end if
	14	else
	15	verified ← FALSE;
	16	end if
		end while
	19
	20	end if
	21	else
	22	AUTH ← TRUE; M ← ∅;
	23	end if
	24	return AUTH, M;
	25	end
		Algorithm 2: Authenticator verification

2 Q ← A U n ∈ AL U ; 3 verified ← TRUE; 4 while Q = ∅ do 5 Get authenticator A from Q; 6 17 if exist event e ∈ L marked) or (verified = FALSE) then 18 AUTH ← FALSE; M ← U;