論文 / 著書情報
Article / Book Information
Title

Performance and Reliability of a Revocation Method Utilizing Encrypted
Backup Data

AuthorKazuki Takayama, Haruo Yokota

Journal/Book nameProc. of IEEE Pacific Rim International Symposium on Dependable
Computing 2009, , , pp. 151-158

発行日 / Issue date2009, 12

権利情報 / Copyright(c)2009 IEEE. Personal use of this material is permitted. However,
permission to reprint/republish this material for advertising or
promotional purposes or for creating new collective works for resale orredistribution to servers or lists, or to reuse any copyrighted componentof this work in other works must be obtained from the IEEE.

Powered by T2R2 (Science Tokyo Research Repository)

2009 15th IEEE Pacific Rim International Symposium on Dependable Computing

Performance and Reliability of a Revocation Method
Utilizing Encrypted Backup Data
Kazuki Takayama
Department of Computer Science
Tokyo Institute of Technology
Tolyo, Japan
Email: takayama@de.cs.titech.ac.jp

Haruo Yokota
Global Scientific Information and Computing CenterTokyo Institute of Technology
Tokyo, Japan
Email: yokota@cs.titech.ac.jp

to disk, while the “encrypt-on-wire” scheme performs theencryption on the fly as the client requests the data. The
former scheme is safer and provides better performance thanthe latter, because it does not use encryption processes forevery read or write operation on the storage side, and it
keeps the data in cipher [4]. However, if files in the network
storage are shared by multiple users, the encrypt-on-disk
scheme must be able to handle the revocation of users.
These files should be reencrypted with a new key whenevera revocation occurs. Active revocation is safe but has accessdenial periods because of the immediate reencryption, while
lazy revocation has no denial period but is unsafe during thedelay [4], [3].
We have proposed a method of handling active revocation
in intelligent storage nodes without the denial period byadopting a primary–backup configuration [5]. Preencrypting
backup data with a key diﬀerent from that used on the
primary store and switching the role of primary and backup
after a revocation realizes a nonstop safe service. It provides
a good combination of security and availability because of
the replication. However, it may cause update performancedegradation because the encryption taking place on the
backup node constitutes an additional load.
Here, we consider delaying the write and reencryption
processes on the backup node to improve update performance. In the delayed write approach, the diﬀerences causedby recent writes are not written to the backup disk immediately but are kept in memory in the backup node. In
the delayed reencryption and write approach, the encryption
operations for the updated data are also delayed. These
approaches have the benefit of utilizing system resources
eﬀectively and aggregating multiple updates for a file but
also have the ill eﬀect of decreasing system reliability bykeeping data in volatile memory. However, the practicaldecrease in reliability is very small because of the sameeﬀect of the nWAL protocol [6]. To demonstrate this, weevaluate the performance of the proposed approaches byexperiments, and the reliability of the system by estimation.
The remainder of this paper is organized as follows. Section II discusses requirements for network storage systems

Abstract—When multiple users access a network storage
system for cloud computing, security becomes a key factor
in the service, as well as performance and reliability. The“encrypt-on-disk” scheme eﬀectively protects transmitted andstored data in network storage. However, this scheme has the
problem of revocation for shared files. Active revocation is safe
but has denial periods to allow immediate reencryption, while
lazy revocation has no denial period but is unsafe during thedelay. We propose intelligent storage nodes capable of handling
active revocation in storage without the denial period by adopting a primary–backup configuration. This approach provides
a good combination of security and availability by replication.
However, the reencryption process negatively aﬀects the update
performance. Delaying the reencryption process and disk writeon the backup node improves performance with no ill eﬀect
on security and a small decrease of MTTDL for the simple
primary–backup configuration. We evaluate the performanceof the proposed approaches by experiments, and the reliability
by estimation.
Keywords-secure storage, revocation, encrypt-on-disk, parallel storage, primary–backup structure

I. Introduction
Network storage is undoubtedly a key component ofcloud computing. The scalability, availability and securityof the storage systems are important requirements for the
cloud computing [1]. There are many types of network
storage systems, including those based on Redundant Arrayof Independent Disks (RAID). However, the most popular
RAID types (types 3–6) have scalability and maintainability problems. The primary–backup configuration guarantees
bandwidth and response time even under disk failures, andeven in a large system. A combination of chained declustering data placement [2] as a form of primary–backup and a
distributed directory is eﬀective to derive scalable bandwidthand low latency.
For the security of the network storage system, data transferred between the network storage system and clients, orwithin the network storage system itself, must be protectedfrom malicious attacks. To implement secure storage systems, several data protection functions have been proposed[3]. The so-called “encrypt-on-disk” scheme protects thetransferred data by encrypting the data as they are stored
978-0-7695-3849-5/09 $26.00 © 2009 IEEE
DOI 10.1109/PRDC.2009.32

151

Authorized licensed use limited to: TOKYO INSTITUTE OF TECHNOLOGY. Downloaded on January 28, 2010 at 20:51 from IEEE Xplore. Restrictions apply.

possessing high performance, availability and maintainability. Section III surveys the current encryption and revocation
techniques in network storage. The proposed approaches are
explained in Section IV. Section V reports experiments toevaluate performance of the proposed approaches. Section
VI estimates their reliability. Finally, Section VII concludes
the paper.

Thus, the approach of the intelligent storage node like theautonomous disk is eﬀective to realize the scalable storage
system. To preserve security as well as performance andavailability, we consider encryption methods suitable for
network storage nodes utilizing the processing facilities on
them.
III. Encryption and Revocation in Network Storage
A. Encrypt-on-disk vs. Encrypt-on-wire

II. Requirements for Network Storage Systems

There are two encryption schemes to protect data transmitted to or from network storage: encrypt-on-wire andencrypt-on-disk [3]. In the encrypt-on-wire scheme, files are
stored in clear text and encrypted only when transmitted,
using a protocol such as secure socket layer (SSL), whilein the encrypt-on-disk scheme, files are stored in cipher andtransmitted without any further encryption process.
From the viewpoint of data transmission performance, theencrypt-on-disk scheme is more eﬃcient than the encrypton-wire scheme, because the storage server in the encrypton-disk scheme does not require as much encryption workas the encrypt-on-wire scheme. Moreover, from the security
point of view, the encrypt-on-disk scheme protects data
while in storage as well as during transmission, while theencrypt-on-write scheme only protects data during transmission.
On the other hand, in a system adopting the encrypt-ondisk scheme for shared files, the files must be reencryptedwith a new key when a revocation occurs. This is because
revoked users can retain the current key, leading to information leakage if they intercept transmitted files despite theiraccess being denied by access control methods. Therefore,
the encrypt-on-disk scheme costs more than the encrypt-onwire scheme when a revocation occurs.

Performance and availability are the most essential properties required for network storage systems for cloud computing. Scalability is also quite significant. A very-large-scale
system configuration should have adequate performancefor its size while ensuring high availability. The costs ofmaintaining a large storage system to satisfy performanceand availability requirements become a crucial problem. The
total amount of storage exceeds the management capabilityof a human administrator who maintains the system.
RAID 3–6 configurations ensure high availability byadopting parity calculation techniques, but their performanceis considerably decreased by the parity calculation for reconstruction if a disk in a parity group fails. Moreover, thescalability of a RAID parity group is restricted for reliability
reasons. On the other hand, multiple RAID groups have theproblems of load balancing and maintainability.
To realize scalable storage systems possessing high performance, high availability and high maintainability, autonomous disks [7] have been proposed. An autonomous
disk system consists of a cluster of highly functional intelligent storage nodes 1 in a networked environment. The
intelligent controller in each storage node is responsible
for balancing the access load in the cluster and handling
failures by migrating data between nodes autonomously. The
absence of a centralized controller in the cluster allows highscalability. To migrate data transparently to the clients, a
distributed directory is necessary. A fat-Btree [8] is adopted
in the autonomous disk system as the distributed directory
to provide high accessibility for data stored in all nodes
with low update overhead, even in large configurations.
This enables each node to migrate data to a neighboringnode without extensive modifications to the whole directory
structure, and hides changes of data location from the clients.
To make the cluster reliable, the autonomous disk system
adopts chained declustering data placement [2] for the
primary–backup configuration, where a neighboring nodeof a primary data node keeps its backup data. Chained
declustering is suited to the Btree-based directory structure
while allowing data to migrate between the neighboring
nodes. The neighboring write-ahead log (nWAL) protocol[6] is eﬀective for asynchronous update of the backup.

B. Active vs. Lazy Revocation
Reencryption methods for revocation in the encrypt-ondisk schema are divided into active revocation and lazy revocation according to the timing of the reencryption [4], [3]. In
active revocation, related files are immediately reencryptedusing a new key after the revocation, while the reencryption
is delayed until the files are next updated in lazy revocation.
Active revocation is more secure than lazy revocation,
because revoked users are immediately unable to decrypt thefiles. However, a weak point of active revocation is that evenauthorized users cannot access the files until the immediate
reencryption processes are completed. This weak point ismore pronounced when multiple revocations occur at thesame time for diﬀerent files.
On the other hand, in lazy revocation, because updateprocesses involve encryption, they can be combined withthe reencryption required for revocation. In addition, thereencryption work for several revocations may be performed
together if the file is not frequently updated. Therefore, lazy
revocation is more eﬃcient than active revocation. However,

1 The concept of the autonomous disk can easily be applied to a multiple
RAID configuration by placing the intelligent controller within each RAID
group.

152

Authorized licensed use limited to: TOKYO INSTITUTE OF TECHNOLOGY. Downloaded on January 28, 2010 at 20:51 from IEEE Xplore. Restrictions apply.

Client

Clientdelay th e re-en cryption

revocation

an d disk write in backu p2) change access path
Controller

updateController

Controller

Controller
re-enc.

re-enc.

K2(F)

K1(F)

Primary3) re-encryptin backgroundPrimary

K3(F)

K2(F)

1) promote
from backup
to primaryPrimary

Primary0) encrypt the fileby the other key

BackupBackupBackupBackupFigure 1.

Backup-assisted revocation

K1(F)Figure 2.

K2(F)Delayed reencryption and write

diﬀerential portion of the file encrypted by K1 , it updates
the primary file and sends the portion to the node storing
its backup. The backup node keeps the portion in memory
but does not reencrypt it using key K2 , nor does it write it
to disk immediately, as shown in Figure 2.
Here, we assume that revocations occur less frequently
than it takes to apply the delayed updates and to reencrypt
files. It seems reasonable in many cases because the revocation occasionally occurs to change the role of members
for some events. Even if revocations occur more frequently,
users wait for the end of reencryption just same as the active
revocation because the amount of delayed updates should besmall for such the short period.
On the other hand, delaying the reencryption process
and disk I/O to some idle period of the CPU and disk,
respectively, can utilize system resources more eﬀectively to
improve performance, multiple updates for the same portion
can be gathered as one update. This is similar to the conceptof lazy revocation but does not have the unsafe period oflazy revocation. Considering the reliability aspect, if we
adopt the single-fault assumption, we can tolerate a disk or anode failure by keeping the update data in volatile memoryon the backup node. This is the same as the concept of
the asynchronous nWAL protocol. Therefore, we evaluatedthe performance eﬀect of the BA-Rev with the delayed
reencryption and disk write, and estimated their reliability.

lazy revocation introduces a security vulnerability, because
files in storage after the revocation and before the update
are encrypted with the old key, which may be kept by therevoked users.
IV. Backup-assisted Revocation
A. Outline of the Proposed Approach
To solve the trade-oﬀ problem between reencryption
methods, we have proposed a method named backupassisted revocation or BA-Rev, in which the files to be used
after revocation are the backup copies, which have been encrypted with a separate key. Figure 1 illustrates the BA-Rev
method, where K1 (F) and K2 (F) mean that the file copies
are encrypted using diﬀerent keys and are treated as theprimary and backup, respectively. After a revocation, K2 (F)is promoted to be the primary, and K1 (F) is reencryptedby the new key K3 . If we adopt the chained declustering
placement, these files are migrated asynchronously to satisfy
any location restrictions. However, it is easy to enable
access during the migration by keeping the source during
the process.
When a reencrypted file is prepared using a new key,
an authorized user given the new key can access the file
immediately after the revocation, but unauthorized users
cannot. The method is therefore as safe as active revocation
because it has no unsafe period, and it provides accessfor authorized users with no denial period following a
revocation.
However, the naive implementation of the BA-Rev isdisadvantaged in its update performance, because a reencryption of the backup data is required for every update.
The reencryption overhead for updates can be reduced bypartial update with block encryption, which does not require
reencryption of the whole file. Moreover, the encryption
process and disk I/O can be delayed to improve update
performance. We call them delayed write or DW and delayed
reencryption and write or DRW, respectively. When the nodestoring the primary file receives an update request with a

B. Related Work
SNAD[9], Plutus[10], and SiRiUS[11] are secure storage
systems that adopt the encrypt-on-disk scheme. The SNAD
paper describes the revocation method as an issue for future
work because of the trade-oﬀ problem. Plutus adopts lazy
revocation, while SiRiUS adopts active revocation. Thesesystems assume an environment in which clients consider
systems to be insecure (systems are not trusted), so they
allow decryption only on client machines. Thus, their policy
is diﬀerent from ours, because we implement reencryption
on storage for eﬃciency reasons. Maat[12] uses automatic
153

Authorized licensed use limited to: TOKYO INSTITUTE OF TECHNOLOGY. Downloaded on January 28, 2010 at 20:51 from IEEE Xplore. Restrictions apply.

(1) active revocation

File object
Key
Object ID

User ID

Signature

User ID

Encrypted key

A

K A+ (K )B

K B+ (K )Reference
Count
Permissions

K n (F [0 ])PA

K n (F [1])PB

K A+ 䋺A’s public key
K 䋺secret key

Figure 3.

Encrypted file

key object

K n (F [m ])•File name•Owner ID•Revocation type
Path
•ReplicaData Disk
•Lockbox
K A+ (K n )AB(disk)

node
A

dec F

read F

ack

node
B

K B+ (K n )enc Ftransfer
file
name

call

write Fack

ack
to client

set keystransfer
enc K
user
name

transfer
K

ack
dec K

read F

dec F

enc F

write F

set keys(2) BA-Rev+
K disk(K n )node
A

K +A ：A’s public key
K n ：secret key

Figure 4.

gen K

transfer
file
name

call

ack

node
B

ack
to clienttransfer
user
name

ack

ack

transfer gen KB
KP

read F

dec F

enc F

write F set keys
to backup

ack
move toprimarydec KP

enc KP

Data structure
Figure 5.

(3) adopt DW strategy to (2)(1) active revocation environment
response timeencrypt dataCtransfer
namePtransfer
key

write to filetransfer
datatransfer
nameresponse
to clientP

Figure 6.

C. Implementation Issues

response
timetransfer
nametransfer
key

response
to primary
re-encrypt data

write to filewrite to file

response timeencrypt dataCP

write to file

(if condition is acceptable)

hold on memory(4) adopt DRW strategy to (2)response
to clienttransfer
datatransferdata

Bresponse
to primary
re-encrypt data～～Ptransfer
key

write to fileBencrypt datatransfer
nameresponse
to clienttransferdata(2) normal BA-Rev environmentCtransfer
datatransfer
key

response
to primary
write to fileB

response timeencrypt dataCtransfer
datatransfer
datatransferdata

Bresponse
to clientwrite to file
response
to primary～～

revocation in the Ceph file system, but they assume a very
short lifetime. On the other hand, our approach is applicableto other systems if they adopt primary-backup configuration.
There are some cryptographic technologies for HDD in
which all stored data are encrypted by a cryptography
processor embedded in the HDD, such as “DriveTrust” by
Seagate Technology and “MTZ2 CJ” by Fujitsu. These
technologies encrypt all data on the HDD to protect thedata if the HDD is lost, which is a diﬀerent policy fromdata transmission protection. However, the cryptography
processor is also useful for our approach.

Process flows for a revocation

hold on memory(if condition is acceptable)
re-encrypt data

write to file

Processes of update in client (C), primary (P), and backup (B)plement reencryption processes. In addition, the lockboxesof backup files in the proposed method contain the primary
decryption keys because the key used with the backup data
must not be known, and so the updated data encrypted withthe primary key are sent to backup when files are updated.
We selected the AES algorithm and ECB mode as theencryption mode. AES is considered to be robust against,
for example, known plaintext attacks. ECB is the mode bywhich data are encrypted in independent blocks, and weused it to enable updates to be implemented by fixed-length
blocks.

Key management is important for systems using cryptography, and should be distributed if storage nodes are tomeet the concept of fully distributed control. We place alockbox which is proposed in SNAD [9] in each storage
node, as a structure storing keys to allow authorized to obtainkeys. Figure 3 shows an example of the lockbox, Key object.
Here, a user x has a public key K x+ and a private key K x− ,and a file is encrypted with a secret key K. Each columnof key object comprises an authorized user’s ID, a secretkey encrypted with the authorized user’s public key, andpermissions. Only the authorized user can obtain the secretkey because the authorized user’s private key is necessary
to decrypt the secret key. The file owner can distribute keys
without communicating directly with sharers. In addition,
storing secret keys so that they can be transmitted “as is”
provides eﬃcient key distribution.
We also use the data structure shown in Figure 4, basedon SNAD. We assume that each user and storage node has apair of public and private keys, (K x+ , K x− ), and that each fileis encrypted with a secret key, Kn . At the time of encryption,
the file is divided into one or more fixed blocks, and eachblock is separately encrypted to decrease the cost of updateby defining the basic unit of updated data.
Each file object has information about the file name, theowner’s ID, the path of the encrypted file, and a lockbox.
Primary file objects also have information identifying thenodes where the backup data are stored. Lockboxes havekeys not only for authorized users but also for the storage
node in which they are stored because this node must im-

D. Process Flows
Process flows for active revocation with the primary–backup structure and BA-Rev are shown Figure 5, andupdate processes with DW and DRW strategies are shownin Figure 6. In the figure, each horizontal arrow indicatesa process implemented in a node or an aspect of parallel
processing in a node, depending on the situation. We omit
disk I/O, file transmission, and index updates from the figure
for simplicity.
Active Revocation:: Primary and backup data arereencrypted immediately. After generating a new secret
key in node A, read, reencrypt, and write operations are
implemented. The key, the file name and the revoked user’sname are concurrently transmitted to node B via anotherthread, and the same process is implemented in node B.
When the processes in node A are completed, notice oftermination is transmitted to the requesting client. If accesses
154

Authorized licensed use limited to: TOKYO INSTITUTE OF TECHNOLOGY. Downloaded on January 28, 2010 at 20:51 from IEEE Xplore. Restrictions apply.

Table I
Configuration of experimental systemCPU
AMD Athlon XP-M1800+ (1.53 GHz)
MemoryPC2100 DDR SDRAM 1 GB
HDD
TOSHIBA MK3019GAX(30 GB, 5400 rpm, B 2.5 inch)
Network
TCP/IP + 1000BASE-T
OS
Linux 2.4.20
Java VM
Sun J2SE SDK 1.5.0 03 Server VM

to the object file are attempted before termination, they areblocked and made to wait until processes are completed.
BA-Rev:: After receiving a revoke request, node Atransmits the information to node B and waits. Node B
deletes the secret key for revoked users stored in the fileobject for backup data, sets the backup as the new primarydata, and notifies process termination to node A. Because
the new primary data are ready at this point, node A notifies
termination to the client. If an access request to the object
is received before this time, the system makes it wait andreturns a request to reaccess together with information about
the location of the data after process completion. Next, node
A receives the key for the new primary data from node B
and stores it in the lockbox of the new backup data for use
when the file is updated. Finally, the new backup data arereencrypted with a new key and set as the backup in nodeA.
DW Strategy:: In the update process in backup, theprocess of writing the updated data (which are alreadyreencrypted with the key used to the backup data) to thefile is delayed. Unapplied updated data are kept in memory.
DRW Strategy:: The processes of reencrypting andwriting updated data are delayed, and they are also kept inmemory.
We consider four timings to write the unapplied updated
data kept on memory into the backup disk in DW and DRW
strategies:
T1: when a revocation occurs,
T2: when the amount of unapplied updated data exceeds
a threshold (to avoid exceeding the limit of memory
resources), andT3: when one of the following conditions are satisfied
T3a: after a constant period of time, andT3b: when the load is less than a threshold.

the node waits to apply the updated data for n seconds
after an update occurs, and after that, applies the update.
If another update request for the same file is performed
within n seconds, the new data replace or augment the
updated data kept in memory.
v) BA-Rev + DWload:n /DRWload:n : In addition to iii), thetiming T3b is used. Defining n as a control parameter,each node checks the number of active threads at aconstant interval, then applies the unapplied updated
data if the number is lower than n. This process isrepeated until the condition is fulfilled.
A. Experimental Environment
We developed a client–server program running on a PC
cluster with the specification listed in Table I. Table II shows
the parameters used in the experiments. The initial allocationof data among the servers follows chained declustering [2],in which backup data are stored in a neighboring node of
the server storing the primary data. The client program sends
requests to GET or UPDATE a file and measures response
times for the requests. The definition of the response timefor UPDATE for each method is shown in Figure 6. The
client also sends requests to revoke or authorize a user’s
access permission for a file.
The interval for GET or UPDATE requests is determinedby an exponential distribution f (t) = λe−λt in which theaverage arrival rate is 1/λ. The request type is selected inaccordance with the GET:UPDATE ratio, which is fixed at
50:50 in this paper. The objects of GET and UPDATE are
selected from files stored in a corresponding storage nodein accordance with a Zipf distribution [13] with parameterθ.

V. Experiments
We have performed experiments to evaluate the performance of BA-Rev with the DW and DRW strategies for thefollowing cases.
i) Active Revocation: When a revocation occurs and theprimary and backup data are encrypted with the samekey.
ii) BA-Rev: When a revocation occurs and the primaryand backup data are encrypted with diﬀerent keys.
iii) BA-Rev + DWraw /DRWraw : In addition to ii), the DW
and DRW strategies are applied to update processes.
The timing for their application is T1 or T2 describedin the previous section. Each storage node checks theamount of unapplied updated data at a constant interval
and applies the updates if the amount exceeds thethreshold.
iv) BA-Rev + DWconst:n /DRWconst:n : In addition to iii), thetiming T3a is used. Defining n as a control parameter,

B. Response Times of Usual Accesses
We first evaluated response performance without revocation. We used three storage nodes, each of which initiallystored 500 files of size 1 MB. A client node sent GET or
UPDATE requests to a storage node, and nodes were selectedwith equal probability. We measured the average responsetime as the average arrival interval decreased from 500 ms
to 150 ms.
The performance of GET was about the same in all cases
because the process of GET was the same in all cases.
Therefore, we omit the graphs of response times for GET.
155

Authorized licensed use limited to: TOKYO INSTITUTE OF TECHNOLOGY. Downloaded on January 28, 2010 at 20:51 from IEEE Xplore. Restrictions apply.

250
200
150
100
50
0
500

450

400
350
300
250
Average arrival interval [ms]

200

150

350
300
250
200

node Anode Bnode C

2000

2000
1800
1600

150
100

1400
1200
1000
800

1500

1000

600

50
0
500

node Anode Bnode C

2200

activeBA-Rev+DRWraw+DRWconst:5+DRWconst:10+DRWload:3+DRWload:5+DRWload:10

Average response time [ms]

300

2500

400
activeBA-Rev+DWraw+DWconst:5+DWconst:10+DWload:3+DWload:5+DWload:10

Average response time [ms]350

Average response time [ms]Average response time [ms]

400

500

400

450

400
350
300
250
Average arrival interval [ms]

200

150

200
0
active0activeFigure 7. Average response times Figure 8. Average response times
for UPDATE with DW strategy
for UPDATE with DRW strategy

BA-Rev

DWraw

DWconst:5

DWload:5

DRWraw

BA-Rev

DWraw

DWconst:5

DWload:5

DRWraw

DRWcosnt:5 DRWload:5

DRWcosnt:5 DRWload:5

Figure 10. Average response times
Figure 9. Average response times
for concentrated revocations (UPfor concentrated revocations (GET)
DATE)
600

Figures 7 and 8 show the average response times of
UPDATE with the DW and DRW strategies, respectively.
Comparing BA-Rev and active revocation, the response timeof UPDATE with BA-Rev is longer: reencryption of the
updated data for backup must be processed because diﬀerent
keys are used for primary and backup.
There was little benefit in applying the DW strategy to
BA-Rev in all applied conditions of updated data, because
the writing to disk is processed quickly by caching the
updated data in this experiment. On the other hand, the DRW
strategy significantly improved the UPDATE performance of
BA-Rev, because the reencryption process is rather resource
consuming. Comparing the performances in each case, although the performance in DRWload:10 is slightly inferior
because it includes the case in which multiple updated data
are applied at high load, the performances in other cases
are equivalent because there are both merits and demerits ineach case.

600

500

Average response time [ms]Average response time [ms]

500

400

300

400

300

200

200

100
100

0
active0activeBA-Rev

DWraw

DWconst:5

DWload:5

DRWraw

BA-Rev

DWraw

DWconst:5

DWload:5

DRWraw

DRWconst:5 DRWload:5

DRWconst:5 DRWload:5

Figure 11. Average response times
for distributed revocations (GET)

Figure 12.
Average response
times for distributed revocations(UPDATE)

for BA-Rev with or without DW and DRW are equivalent
to, or slightly larger than, those for active revocation. Thisis for the reasons given in V-B. However, compared withthe results at nodes B and C, the diﬀerence is small.
Comparing DW and DRW with BA-Rev, these strategies provide better GET performance, especially in node
B. This is because they reduce the number of writes of
updated data in the backup. For UPDATE, policy DRW, inwhich reencryption of updated data is delayed, has better
performance than BA-Rev with DW. Thus, the reencryption
process is susceptible to revocation processes, which also
involve reencryption.

C. Under Concentrated Revocations
To evaluate the influence of revocations, we measured
response times when revocations occurred in a storage node.
We used three storage nodes, A, B, and C, and three client
nodes for this experiment. The backup data corresponding to
the primary data stored in node A (B, C) were stored in node
B (C, A). We fixed the average arrival interval of accesses at
400 ms, and the parameter n for DW or DRW was five. We
enforced the multiple revocation processes for 50 files stored
in node B simultaneously and measured response times of
100 GETs or UPDATEs, which were performed in the period
containing the start and the end of the revocation processes.
We performed this experiment six times.
Figures 9 and 10 show average response times and 95
percent confidence intervals for each storage node under theabove conditions. With BA-Rev with or without DW and
DRW, the response times of GET and UPDATE at node B
storing target files of the revocation and at node C, which
stores their backup data, are shorter than that for active
revocation. This is because no reencryption for revocations
was necessary in node C in BA-Rev, with or without DW
and DRW. The reencryption was executed in node B, but thetarget of reencryption is backup data, which are not accessedfrom clients. On the other hand, at node A, response times

D. Under Distributed Revocation
To evaluate the mutual influence of multiple revocations
occurring in contiguous storage nodes, we distributed thetarget files for revocation to all three storage nodes. We
enforced multiple revocations for 15 files in each storage
node and measured the response times of 100 accesses
during the revocations. We performed this experiment six
times.
Figures 11 and 12 show average response times and 95
percent confidence intervals for all storage nodes. Comparing BA-Rev, DW and DRW with active revocation, each
proposed environment has better performance for both GET
and UPDATE, similar to the results for the concentrated
revocation examined above. In particular, the response timeof UPDATE with DRW is the shortest, while those for other
BA-Rev with or without DW and those of GET are nearly
equivalent. The reason for the equivalent results is that theload per storage node is low in this experiment because of
156

Authorized licensed use limited to: TOKYO INSTITUTE OF TECHNOLOGY. Downloaded on January 28, 2010 at 20:51 from IEEE Xplore. Restrictions apply.

Table III
Definition of parameter for MTTDL
MT BF Disk(Power)
MTBF of HDD, or power supply system
MT T RDisk
MTTR of the HDD
N
number of storage nodesMmaximum bandwidth of a storage nodeRbandwidth the node can allocate to repair
S
scale factor about the correlate disk failurePprobability of successfully reading all disk sectors
E
the processing speed for re-encryption

therefore calculated as follows, and the overall MT T DLDisk
is calculated as the harmonic average of the individual
MTTDLs.

the distributed revocation targets to multiple nodes. This
result indicates that the BA-Rev realizes steadily better
performance than that with active revocation, regardless ofthe method of applying updated data, if the number of
revocation objects per node is not large.

MT T DLDF=

MT BF Disk×N

MT T DLCDF=

MT BF Disk
×
N

=

⎛
⎞ DiskS ize 
1 ⎟⎟⎟⎟ 512
MT BF Disk
1⎜⎜⎜⎜
, P = ⎜⎝1 − BER ⎟⎠ (4)×N
1 − P24096

MT T DLU BE

1(2)

MT T RDisk
MT BF Disk /2

1(3)

MT T RDisk
MT BF Disk /S /2

C. Reliability with DW and DRW
For the DW or DRW strategies, there are two combinations of failures that cause loss of data: one is a combinationof storage nodes failing, and the other is a combination of asingle node failure and a power failure. We deal with theseseparately.
1) MTTDL for Storage Node Failures: The calculation
method is the same as in VI-B, except MT T RDisk . With
the DW or DRW strategies, when backup data are set as
primary to repair, the updated data that are unapplied must
be applied. Therefore, MT T RDisk is longer (because of thewriting of the updated data in the DW strategy, and becauseof the reencrypting and writing of them in the DRW strategy)
than defined in formula 1.
2) MTTDL for Storage Node and Power Failure: Whena power supply fails, the updated data kept in memory are
lost. Therefore, a storage node must send the primary data
to the neighboring node to repair the backup data. About adisk’s quantity of data must be transferred per node in theworst case, so the formula for MT T RPower is the same as
formula 1.
There are two patterns in which data are lost withpower supply failure: when the power supply fails and any
disk error follows before the repair is completed (P →{DF, CDF, U BE}); and when any single node fails and apower failure follows before the repair (D → P). In the latter
case, strictly speaking, data are not lost if the updated data
have already been applied, but we assume that this situation
occurs negligibly often in this paper.
Each MTTDL is as follows, and MT T DLPower is also
calculated by the harmonic average of them.

VI. Reliability Estimation
With the DW and DRW strategies, data are temporarily
inconsistent between the primary and backup disks because
the updated data for backup are kept in memory. Therefore,
there is the possibility of data loss from the combinationof a disk failure and a power fault, even if the data are
redundant because of the primary–backup structure. In thissection, we estimate and compare Mean Time To Data
Loss (MTTDL) of the normal environment adopting chained
declustering (with active revocation or primitive BA-Rev) in
the environment with DW or DRW.
A. Deriving MTTDLWe derived MTTDL using the method described in [14],and the parameters are defined in Table III. We use threefactors for HDD failure: disk failure (DF), correlated disk
failure (CDF), and unrecoverable bit error (UBE). For CDF,
failures are commonly based on environmental factors (e.g.,
earthquakes, power dips and surges) and manufacturing
factors (e.g., early or late failures in disk drives) [14],taking into account the higher probability of subsequentdisk failures. With the UBE, the bit error rate (BER) is
considered, this being the probability of encountering single
bit errors.
B. Reliability with Chained Declustering
When a failure on storage node (k) occurs in the environment with chained declustering, the neighboring node (k +1)
must set the backup data as the new primary, receive the datafrom node (k − 1) for the backups lost on node k, and send
the new primary to node (k + 2) to repair the redundancy.
Therefore, the amount of data to be transferred is the disk
size at worst, so MT T RDisk is as follows.
DiskS ize
MT T RDisk =
[hrs]
(1)
M × R × 3600
MTTDL can be calculated for each factor of failure independently. With chained declustering, data are lost if one
storage node has failed and one of the two neighboring nodes
also fails before the repair has completed. Each MTTDL is1

MT T DLP→DF=MT BF Power ×

MT T DLP→CDF=

MT BF Power ×

MT T DLP→U BE=

MT BF Power ×

MT T DLD→P=MT BF Disk× MT T R
DiskN

MT T RPowerMT BF Disk /N

1
MT T RPowerMT BF Disk /S /N

1
1 − PN1

MT BF Power

157

Authorized licensed use limited to: TOKYO INSTITUTE OF TECHNOLOGY. Downloaded on January 28, 2010 at 20:51 from IEEE Xplore. Restrictions apply.

(5)
(6)
(7)
(8)

Mean time [hrs]108

MTTDLDisk:CD
MTTDLDisk:DW
MTTDLPower:DW
MTTDLDisk:DRW
MTTDLPower:DRW

7

10

106

105

0

8

16

24

32
N

40

48

56

64

Figure 13.
The MTTDL of disk
failure in each environment and of
power failure with DW/DRW

In future work, we plan to evaluate the proposed approachin actual environments including diﬀerent types and sizes offiles accessed from heterogeneous applications.

Table IV
Estimation parameters
Disk size
500 GB
1.2 × 106 hrs
MT BF Disk
MT BF Power1.752 × 106 hrs
BER
10−14
M
300 MB/s
R
0.5
S
10
E
2 MB/s

Acknowledgments
This research was partially sponsored by CREST of JST(Japan Science and Technology Agency) and MEXT, via a
Grant-in-Aid for Scientific Research #19024028.
References[1] Brian Hayes. Cloud Computing. CACM, 51(7):9–11, 2008.
[2] Hui-I Hsiao and David J. DeWitt. Chained Declustering:
A New Availability Strategy for Multiprocessor Database
Machines. In Proc. of ICDE’90, pages 456–465, 1990.

D. Discussion
We compared MTTDLs in the environment with thechained declustering (CD) and that with DW or DRW. The
parameters for estimation are listed in Table IV, referring to[14], [15] to select these values.
Figure 13 shows the MTTDL for disk failures in eachenvironment and that with power failure with the DW or
DRW strategies. The lines of CD, DW, and DRW of MTTDL
for disk failures (MT T DLDisk ) are almost overlapped, andthe diﬀerence is smaller than one percent of MTTDLs. In
addition, MT T DLPower , which expresses the probability ofdata loss caused by power supply failure in the environment
with DW or DRW, is much larger than MT T DLDisk . For
example, in the case of N = 32, MT T DLPower is about
107 hours while MT T DLDisk is about 106 hours for the
given parameters. Therefore, we can say that reliability
degradation with DW and DRW is very small.

[3] Paul Stanton. Securing Data in Storage: A Review of Current
Research. ArXiv Computer Science e-prints, 2004.
[4] Erik Riedel, Mahesh Kallahalla, and Ram Swaminathan. A
framework for evaluating storage system security. In Proc.
of FAST ’02, pages 15–30, 2002.
[5] Kazuki Takayama. Compatibility of performacne and security in distribute storage system storing encrypted data (injapanese). Master’s thesis, Dep. of Computer Science, Tokyo
Institute of Technology, 2009.
[6] Svein-Olaf Hvasshovd. Recovery in Parallel Database Systems. 1996.
[7] Haruo Yokota. Autonomous Disks for Advanced Database
Applications. In Proc. of DANTE’99, pages 435–442, 1999.
[8] Haruo Yokota, Yasuhiko Kanemasa, and Jun Miyazaki. FatBtree: An Update-Conscious Parallel Directory Structure. In
Proc. of ICDE1999, pages 448–457, 1999.

VII. Conclusions
We have proposed backup-assisted revocation (BA-Rev)with delayed write (DW), and with delayed reencryption
and write (DRW). BA-Rev is a more eﬃcient reencryption
method for revocation in the encrypt-on-disk system than
the active revocation method, and more secure than lazy
revocation. By substituting the backup data encrypted witha key diﬀerent from that of the primary for the primarydata when a revocation occurs, the revocation is completed
rapidly at low cost. To improve the update performancedecreased by the backup handling, the reencryption process
and disk write on the backup node are delayed, which has noill eﬀect on security and a very small decrease in reliability.
The experimental results using a PC cluster show thatthe proposed approach greatly reduces the average response
times of accesses when revocations occur compared withactive revocation. In addition, DRW achieves update performance equivalent to active revocation, and improved
revocation performance. The estimation of reliability showsthat the decrease in MTTDL by the DW and DRW issmaller than one percent of MTTDL for the normal chained
declustering. Those results demonstrates that the proposed
approach provides high performance and availability forsecure network storage systems.

[9] Ethan Miller, Darrell Long, William Freeman, and BenjaminReed. Strong Security for Network-Attached Storage. In
Proc. FAST ’02, pages 1–13, 2002.
[10] Mahesh Kallahalla, Erik Riedel, Ram Swaminathan, Qian
Wang, and Kevin Fu. Plutus: Scalable Secure File Sharing on
Untrusted Storage. In Proc. of FAST’03, pages 29–42, 2003.
[11] Eu-Jin Goh, Hovav Shacham, Nagendra Modadugu, and Dan
Boneh. SiRiUS: Securing Remote Untrusted Storage. In Proc.
of ISOC and NDSS Sympo. 2003, 2003.
[12] Andrew W. Leung, Ethan L. Miller, and Stephanie Jones.
Scalable Security for Petascale Parallel File Systems. In Proc.
of SC07, pages 1–12, 2007.
[13] Donald E. Knuth. Sorting and Searching. Addison-Wesley
Publishing Company, 1973.
[14] Edward Michael Macdonald. Designing Reliable Large-Scale
Storage Arrays. Master’s thesis, Florida State University,
College of Engineering, 2007.
[15] Frank Bodi. ”DC-Grade” Reliability for UPS in Telecommunications Data Centers. In Proc. of 29th INTELEC, pages
595–602, 2007.

158

Authorized licensed use limited to: TOKYO INSTITUTE OF TECHNOLOGY. Downloaded on January 28, 2010 at 20:51 from IEEE Xplore. Restrictions apply.