17.2.1 Data Organization in Version Control Systems

In software development, version control systems have been used broadly in managing source code, documentation, and configuration files. Typically, the VCS clients interact with a VCS server and the VCS server stores all the changes to the data in a main repository, such that an arbitrary version of the data can be retrieved at any time in the future. Each VCS client has a local repository, which stores the working copy (i.e., the version of the data that was last checked out by the client from the main VCS repository), the changes made by the client to the working copy, and some metadata.

A version control system provides several useful features that can allow the users to track and control changes made to the data over time. Such features include operations like commit, update, branch, revert, merge, and log. In practice, the most commonly used operations are commit and retrieve. Commit refers to the process of submitting the latest changes of data to the main repository, so that the changes to the working copy become permanent. Retrieve refers to the process of replacing the working copy with an older or a newer version stored on the server.

Version control systems using delta encoding. A version control system keeps track of all the changes made to the data over time. In this way, any version of the data can be retrieved if necessary. A key issue here is how to store and organize all those changes in the VCS repository. A straightforward approach could be simply storing each individual data version upon a commit. This simple approach was adopted by CVS [3] when storing binary files. A significant disadvantage of this approach is the large bandwidth and storage space it requires for committing a file version, especially when the file size is large.

By observing that there is always a large amount of duplicate content between each file version and its subsequent file version, modern version control systems adopt “delta encoding” to reduce the storage space being needed. Using delta decoding, a version control system only stores the first version of a file in its entirety, and for each subsequent version of the file, the VCS only stores the difference between this file version and its immediate previous version. All the differences are recorded in discrete files called “deltas.”

Therefore, if there are t file versions in total, the VCS server will store them as the initial file and $t-1$ deltas (see Fig. 17.1). Popular version control systems that use variants of delta encoding include CVS [3], SVN [14], and Git [8]. The delta encoding can significantly reduce the storage space required to store all the file versions. However, it suffers from an expensive retrieval: To retrieve the file version t, the VCS server needs to start from the initial file version and apply all the subsequent deltas up to version t, incurring a cost linear in t (see Fig. 17.1). Considering that source code repositories may have a large number of file versions (e.g., GCC has more than 200,000 versions in its repository [7]), retrieving an arbitrary file version may bring a significant burden to the VCS server.

Version control systems using skip delta encoding. As a special type of delta encoding, the skip delta encoding is designed to further optimize the retrieval cost. Apache Subversion (SVN [14]) is a popular version control system that adopts this type of delta encoding. In skip delta encoding, each new file version is still stored as the difference between it and a previous file version. The main difference between the skip delta encoding and the delta encoding is that this previous file version is not necessarily the immediate previous version. Instead, it can be an arbitrary file version from the initial file version up to the immediate previous file version. This ensures that retrieval of an arbitrary file version t requires significantly less than t applications of deltas by the version control server. In this case, the difference is called a “skip delta” and the old version against which a new version is encoded is called a “skip version.”

In particular, if we select the skip version based on the following rule, the complexity for retrieving an arbitrary file version t will be $\mathrm{O}(\log (t))$, i.e., we only need to apply at most $\log (t)$ skip deltas in order to recompute the desired file version t starting from the initial file version. Let version j be the skip version of version i. The rule for selecting the skip version j is: Based on the binary representation of i, we change the rightmost bit that has value “1” into a bit with value “0”. For example, in Fig. 17.2, version 3's skip version is version 2. This is because the binary representation of 3 is 011, and by changing the rightmost “1” bit into a “0” bit, we can obtain 2.

By using the skip delta encoding, the cost for recovering an arbitrary file version will be logarithmic in the total number of versions. For example, in Fig. 17.2, to reconstruct version 3, we can start from version 0 and apply ${\delta }_2$ and ${\delta }_3$; to reconstruct version 4, we can start from version 0 and apply ${\delta }_4$. The skip version for version 25 is 24, whose skip version is 16, whose skip version is 0. Thus, to reconstruct version 25, we can start from version 0 and apply ${\delta }_{16}$, ${\delta }_{24}$, and ${\delta }_{25}$. We prove that the cost for retrieving an arbitrary file version t is bounded by $\mathrm{O}(\log (t))$ [24].

17.2.2 Remote Data Integrity Checking (RDIC)

Remote Data Integrity Checking (RDIC) is framework that allows a data owner to verify the integrity of the data outsourced to an untrusted third party. RDIC usually relies on two key steps: (i) Data preprocessing. The data to be outsourced are pre-processed by the data owner, generating metadata (e.g., integrity tags) which can be used to verify whether the data have been tampered with over time; (ii) Periodical checking. After the data have been outsourced, a verifier (e.g., the data owner or a third-party verifier) will periodically issue a challenge request to ask the storage server to prove possession of the outsourced data. The existing PDP [18,19] and PoR [20,30] are two popular RDIC designs, in which the checking step is highly optimized by utilizing a novel “spot-checking” technique. Rather than simply verify the entire outsourced data, which may be prohibitively expensive, the spot-checking technique checks a random subset of the entire outsourced data. Prior work [18,19] shows that if an adversary corrupts a certain amount of the data, the spot-checking technique can detect such a corruption with high probability by checking a few randomly selected blocks.

RDIC has been recently extended to a dynamic setting [22,25,27,33] and a distributed setting [21,23,26,29].

17.4.1 Definition of AVCS

The AVCS relies on seven polynomial-time algorithms: KeyGen, ComputeDelta, GenMetadata, GenProof, CheckProof, GenRetrieveVersionAndProof, and CheckRetrieveProof.

KeyGen is a key generation algorithm run by the client to initiate the entire version control system.

ComputeDelta is a delta generation algorithm run by the client to compute the corresponding delta when committing a new file version.

GenMetadata is a metadata generation algorithm run by the client to generate the verification metadata for a new file version before committing it.

GenProof is an algorithm run by the server to generate a proof of data possession.

CheckProof is an algorithm run by the client to verify the proof of data possession.

GenRetrieveVersionAndProof is an algorithm run by the server to generate the correctness proof of a retrieved file version.

CheckRetrieveProof is an algorithm run by the client to verify the correctness of the retrieved file version.

Utilizing the aforementioned algorithms, we build an AVCS divided into four phases: Setup, Commit, Challenge, and Retrieve.

Setup. The client runs KeyGen to generate the private key material and performs other initialization operations.

Commit. To commit a new file version, the client runs ComputeDelta and GenMetadata to compute the delta and the metadata for the new file version, respectively. The delta and the metadata are both sent to store at the server.

Challenge. Periodically, the verifier (the client or a third-party verifier) challenges the server to obtain a proof that the server continues to store all the file versions stored by the client. The server uses GenProof to compute a proof of data possession and sends back the proof. The client then uses CheckProof to validate the received proof.

Retrieve. The client requests an arbitrary file version. The server runs GenRetrieveVersionAndProof to obtain the requested file version, together with a proof of correctness. The client verifies the correctness of the retrieved file by running CheckRetrieveProof.

Note that this definition encompasses version control systems that use delta encoding, which also include skip delta-based version control systems.

17.4.2 An AVCS Construction

Whereas our AVCS definition targets version control systems that use delta encoding in general, in the construction we focus on version control systems that use skip delta encoding, because: First, they are optimized for both storage and retrieval; Second, they are arguably more challenging to secure than version control systems that use delta encoding, due to the additional complexity of computing the skip deltas.

Challenges. To instantiate the AVCS construction for skip delta-based version control systems, we need to address several challenges. These challenges stem from the adversarial nature of the VCS server that is hosted in the untrusted clouds and from the format of a skip delta-based VCS repository being optimized to minimize the server's storage and workload during the Retrieve phase.

The first challenge comes from the gap between the server's and the client's view of the repository. In a general-purpose RDIC protocol (Section 17.2.2), the client and the server have the same view of the outsourced data: the client computes the verification metadata based on the data, and then sends both data and metadata to the server. The server stores these unmodified. Additionally, the server stores and uses the data and metadata to answer the verifier's challenges by computing a proof that convinces the verifier that the server continues to store the exact data outsourced by the data owner.

However, in a skip delta-based VCS, there is a gap between the two views (Fig. 17.3), which makes skip delta-based VCS systems more difficult to audit: Although both the client and server view the main VCS repository as the initial version of the data plus a series of delta files corresponding to subsequent data versions, they have a different understanding of the delta files. To commit a new version t, the client computes and sends to the server a delta that is the difference between the new version and its immediate previous version, i.e., the difference between version t and $t-1$. However, this delta is different from the skip deltas that are stored by the server: a ${\delta }_t$ file stored by the server is the difference between version t and its “skip version”, which is not necessarily the version immediately previous to version t. Since the client does not have access to the skip deltas stored by the server, it cannot compute the verification metadata over them, as needed in the RDIC protocol.

The second challenge is due to the fact that delta encoding is not reversible. The client may try to retrieve the skip delta computed by the server and then compute the verification metadata based on the retrieved skip delta. However, in an adversarial setting, the client cannot trust the server to provide a correct skip delta value. This is exacerbated by the fact that the delta encoding is not a reversible operation (Fig. 17.4). Specifically, if ${\delta }_{t-1\to t}$ is the difference between versions $t-1$ and t (i.e., $F_t=F_{t-1}+{\delta }_{t-1\to t}$), this does not imply that version $t-1$ can be obtained based on version t and ${\delta }_{t-1\to t}$. The reason comes from the method used by delta encoding to encode update operations between versions, such as insert, update, and delete. If a delete operation was executed on version $t-1$ to obtain version t, then ${\delta }_{t-1\to t}$ encodes only the position of the deleted portion from version $t-1$, so that given version $t-1$ and ${\delta }_{t-1\to t}$, one can obtain version t. However, ${\delta }_{t-1\to t}$ does not encode the actual data that has been deleted. Thus, version $t-1$ cannot be obtained based on version t and ${\delta }_{t-1\to t}$.

High-level idea. We present an AVCS construction that can resolve the aforementioned challenges. The idea behind our construction is that we allow the client and the untrusted server to collaborate to compute the skip deltas. By sacrificing an acceptable amount of communication, we successfully eliminate the need of storing a large number of previous versions in the client (for the purpose of computing skip deltas), and thus are able to conform to the notion of storage outsourcing.

17.4.2.1 Construction details

The version control repository stores t file versions, $F_0,F_1,\dots ,F_{t-1}$. They are stored in the repository using skip delta encoding as: $F_0$, ${\delta }_1,{\delta }_2,\dots ,{\delta }_{t-1}$ (i.e., the initial file version and $t-1$ skip delta files). We view the entire information pertaining to the t versions of the file F as a virtual file $\tilde{F}$, which is obtained by concatenating the original file version and all the $t-1$ subsequent delta files: $\tilde{F}=F_0\Vert {\delta }_1\Vert {\delta }_2\Vert \dots \Vert {\delta }_{t-1}$. We view $\tilde{F}$ as a collection of fixed-size blocks, and each block containing s symbols (a symbol is an element from $\mathit{GF}(p)$, where p is a large prime (at least 80 bits)). This view matches the view of a file in an RDIC scheme: To check the integrity of all the versions of F, it is enough to check the integrity of $\tilde{F}$. Let n denote the number of blocks in $\tilde{F}$. As the client keeps committing new file versions, n will grow accordingly (note that n is maintained by the client).

We use two types of verification tags. To check data possession (in the Challenge phase), we use challenge tags, which are computed over the blocks in $\tilde{F}$ to facilitate spot checking technique in RDIC (Section 17.2.2). The challenge tag is computed for each block following the manner of private verification tag construction in [32], which is homomorphically verifiable. To check the integrity of individual file versions (in both the Commit and the Retrieve phases), we use retrieve tags, each of which is computed over an entire version of F. The retrieve tag is computed using HMAC [29] over the whole file version and its version number.

In a benign setting, whenever the client commits a new file version, the server computes and stores a skip delta file in the main VCS repository. Under an adversarial setting, to leverage RDIC techniques over the VCS repository, the skip delta files must be accompanied by challenge tags. Since the challenge tags can only be computed by the client, in our construction, we require the client to compute the skip delta, generate the challenge tags over it, and send both the skip delta and the tags to the server. An overview of our AVCS construction is shown in Fig. 17.5.

In the following, we elaborate the design of our AVCS construction for each phase: setup, commit, challenge, and retrieve.

Setup. The client selects two private keys $K_1$ and $K_2$ uniformly at random from a large domain (this is determined by the security parameters). It also initializes n as 0.

Commit. As shown in Fig. 17.6, when committing a new version $F_i$, where $i>0$, the client must compute the skip delta (${\delta }_{\mathit{skip}}$) for $F_i$. The ${\delta }_{\mathit{skip}}$ must be computed against a certain previous version of the file, called the “skip version” (refer to Section 17.2.1). Let $\mathit{skip}(i)$ be the skip version of version i. Note that the client also has in its local store a copy of $F_{i-1}$, which is the working copy.

The client will check if $\mathit{skip}(i)$ is version $i-1$. If it is true, the client can directly compute ${\delta }_{\mathit{skip}}$ such that $F_i=F_{i-1}+{\delta }_{\mathit{skip}}$. Otherwise, the client computes ${\delta }_{\mathit{skip}}$ by interacting with the VCS server using the following steps (see Fig. 17.6):

1.  The client computes the difference between the new version and its immediate previous version, i.e., computes δ such that $F_i=F_{i-1}+\delta$. The client then sends δ to the server.

2.  The server recomputes $F_{i-1}$ based on the data in the repository and then computes $F_i=F_{i-1}+\delta$. The server then recomputes $F_{\mathit{skip}(i)}$ (the skip version for $F_i$) based on the data in the repository and computes the difference between $F_i$ and $F_{\mathit{skip}(i)}$, i.e., it computes ${\delta }_{\mathit{reverse}}$ such that $F_{\mathit{skip}(i)}=F_i+{\delta }_{\mathit{reverse}}$. The server sends ${\delta }_{\mathit{reverse}}$ to the client, together with the retrieve tag for $F_{\mathit{skip}(i)}$.

3.  The client computes the skip version, $F_{\mathit{skip}(i)}=F_i+{\delta }_{\mathit{reverse}}$, and checks the validity of $F_{\mathit{skip}(i)}$ using the retrieve tag received from the server. The client then computes the skip delta for the new file version, i.e., ${\delta }_{\mathit{skip}}$, such that $F_i=F_{\mathit{skip}(i)}+{\delta }_{\mathit{skip}}$.

To give an example, when the client commits $F_{15}$, the client also has the working copy $F_{14}$, which is the skip version for $F_{15}$, and the client can compute directly ${\delta }_{\mathit{skip}}$ such that $F_{15}=F_{14}+{\delta }_{\mathit{skip}}$. However, when the client commits $F_{20}$, it only has $F_{19}$ in his/her local store and must first retrieve from the server ${\delta }_{\mathit{reverse}}$ and then compute $F_{16}$, which is the skip version for $F_{20}$, as $F_{16}=F_{20}+{\delta }_{\mathit{reverse}}$. Only then can the client compute ${\delta }_{\mathit{skip}}$ such that $F_{20}=F_{16}+{\delta }_{\mathit{skip}}$.

After having computed ${\delta }_{\mathit{skip}}$, the client views ${\delta }_{\mathit{skip}}$ as a collection of blocks, and computes a set of challenge tags using key $K_1$. The client also computes a retrieve tag $R_i$ for $F_i$, using key $K_2$. The set of challenge tags and the retrieve tag $R_i$ will be sent to the VCS server. The client then increases n by x, where x is the number of blocks in ${\delta }_{\mathit{skip}}$. Note that if the file version being committed is the initial file version $F_0$, the client directly computes a set of challenge tags and a retrieve tag over $F_0$.

Challenge. We leverage spot checking technique (see Section 17.2.2) to check the remotely stored CVS repository. Periodically, the client challenges the server to prove data possession of a random subset of the blocks in $\tilde{F}$. The server computes a proof of data possession by using the challenge blocks and their corresponding challenge tags. As the challenge tags are homomorphically verifiable, the server can further reduce the size of the proof by aggregating the challenge blocks and the corresponding challenge tags. The client further checks the proof using key $K_1$. This spot checking mechanism is quite efficient. For example, when the server corrupts 1% of the repository (i.e., 1% of $\tilde{F}$), then the client can detect this corruption with high probability by randomly checking only a small constant number of blocks (e.g., checking 460 blocks results in a 99% detection probability) [18].

Retrieve. The Retrieve phase is activated when the client wants to replace the working copy with an older or a newer version $F_j$. The client sends a retrieval request to the server. The server generates the delta (i.e., δ) of $F_j$ against the client's working copy, together with $F_j$'s retrieve tag $R_j$. Both δ and $R_j$ are returned to the client. The client then computes $F_j$ by applying δ over its working copy, and checks the validity of $F_j$ by using $R_j$ and the key $K_2$.

17.7.1 Theoretical Evaluation

Theoretical analysis on our AVCS construction. During the Commit phase, the client interacts with the version control server to compute skip deltas. To retrieve any file version from the repository, the server only needs to go through at most $\log (t)$ skip deltas. Therefore, the computation complexity in the server is $\mathrm{O}(\log (t))$. The client has to compute the skip version as well as the skip delta, and generate the metadata, which results in a complexity linear to the size of the file version. The communication during the commit phase includes two deltas and a set of challenge tags for a skip delta.

During the Challenge phase, our AVCS uses an efficient spot checking technique: periodically, the client challenges the server, requiring the server to prove data possession of a random subset of data blocks in the entire repository; the server computes a proof by aggregating the selected blocks as well as the corresponding challenge tags. Therefore, both the computation (client and server) and the communication complexities are $\mathrm{O}(1)$. This is a major advantage of the AVCS compared to all the previous approaches, in which the checking complexity is proportional to either the repository size or the version size.

During Retrieve phase, the server needs to go through at most $\log (t)$ skip deltas to compute a target file version. Therefore, the server computation complexity is $\mathrm{O}(\log (t))$. The client stores locally the working copy which requires $\mathrm{O}(n)$ space.

Comparison among different secure version control approaches. We show a performance comparison among our AVCS construction, DPDP [27], and DR-DPDP [28] in Table 17.1. Compared to both DPDP and DR-DPDP, our AVCS has constant complexity in the Challenge phase in terms of both computation and communication. In the Retrieve phase, the AVCS is significantly more efficient than the other approaches in terms of server computation. However, the server computation in the Commit phase of the AVCS is slightly larger than the other approaches due to the overhead for computing the skip deltas. We believe this is not a significant drawback, because: (i) Compared to the other approaches, the AVCS only has an additional logarithmic factor, which is usually small, i.e., for $t=1,000,000$, $\log (t)$ is 20; (ii) The server is hosted in the public clouds, which are usually capable of handling computation intensive tasks.

Table 17.1

Comparison of different RDIC approaches for version control systems (t is the number of versions in the repository and n is the number of blocks in a version)

	DPDP [27]	DR-DPDP [28]	AVCS
Communication (Commit phase)	$\mathrm{O}(n+\log t)$	O(n + 1)	O(n + 1)
Server computation (Commit phase)	$\mathrm{O}(n+\log t)$	O(n)	$\mathrm{O}(n\log t)$
Client computation (Commit phase)	$\mathrm{O}(n+\log t)$	O(n + 1)	O(n + 1)
Communication (Challenge phase)	$\mathrm{O}(\log n+\log t)$	$\mathrm{O}(1+\log n)$	O(1)
Computation (server + client) (Challenge phase)	$\mathrm{O}(\log n+\log t)$	$\mathrm{O}(1+\log n)$	O(1)
Communication (Retrieve phase)	$\mathrm{O}(n+\log t)$	O(n + 1)	O(n + 1)
Server computation (Retrieve phase)	$\mathrm{O}(tn+\log t)$	O(tn + 1)	$\mathrm{O}(n\log t+1)$
Client computation (Retrieve phase)	$\mathrm{O}(n+\log t)$	O(n)	O(n)
Client storage	O(n)	O(n)	O(n)
Server storage	O(nt)	O(nt)	O(nt)

17.7.2 Experimental Evaluation

To understand the impact of AVCS on the real-world VCS systems, we implemented AVCS using a popular open-source version control system, Apache Subversion (SVN) [14] version 1.7.8. As we know, many projects are using SVN for source control management. This includes FreeBSD [6], GCC [7], Wireshark [15], as well as all the open-source projects in Apache Software Foundation [1], etc.

Implementation. We modified the source code of both the client and the server of SVN. For the client, we mainly modified five SVN commands: svn add, svn rm, svn commit, svn co, and svn update. For the server, we modified the stand-alone server “svnserve.” The implementation details as well as implementation issues can be found in our conference paper [24].

Experimental results: We evaluated both the computation and the communication overhead during the Commit phase and the computation overhead during the Retrieve phase, for both SSVN and SVN. We selected three representative public SVN repositories for our experimental evaluation: FileZilla [5], Wireshark [15], and GCC [7]. The Challenge phase has been shown to be very efficient when using spot-checking technique [19], so we do not include it in this evaluation. The detailed experimental results can be found in our conference paper [24], which shows that AVCS only incurs a modest decrease in performance to the original SVN system.