Efficient and Secure Content Processing and Distribution by Cooperative Intermediaries
INTRODUCTION
IN order to enhance the performance of content distribution
networks (CDNs), several approaches have been
developed based on the use of content management services
provided by intermediary proxies. In most of these approaches,
content caching is the main service provided by
proxies [1], [3], [15], [18]. That is, instead of asking a content
server for contents upon each client request, a proxy first
checks if these contents are locally cached. Only when the
requested contents are not cached or out of date are the
contents transferred from the content server to the clients. If
there is a cache hit, the network bandwidth consumption
can be reduced. A cache hit also reduces access latency for
the clients. System performance thus improves, especially
when a large amount of data is involved. Besides these
improvements, caching makes the system robust by letting
caching proxies provide content distribution services when
the server is not available.
With the emergence of various network appliances and
heterogeneous client environments, there are other relevant
new requirements for content services by intermediaries [2],
[10]. For example, content may be transformed to satisfy the
requirements of a client’s security policy, device capabilities,
preferences, and so forth. Therefore, several content services
have been identified that include but are not limited to
content transcoding [2], [5], [10], [13], in which data is
transformed from one format into another, data filtering, and
value-added services such as watermarking [7]. Other
relevant services are related to personalization, according to
which special-purpose proxies can tailor the contents based
on user preferences, current activities, and past access
history.
Many studies have been carried out on intermediary
content services [2], [5], [10], [13]; however, the problem of
data security in these settings has not caught much
attention. Confidentiality and integrity are two main
security properties that must be ensured for data in several
distributed cooperative application domains such as collaborative
e-commerce [20], distance learning, telemedicine,
and e-government. Confidentiality means that data can only
be accessed under the proper authorizations. Integrity
means that data can only be modified by authorized
subjects. The approaches developed for securely transferring
data from a server to clients are not suitable when data
is to be transformed by intermediaries. When a proxy
mediates data transmission, if the data is enciphered during
transmission, security is ensured; however, it is impossible
for intermediaries to modify the data. On the other hand,
when intermediaries are allowed to modify the data, it is
difficult to enforce security.
Much previous work has been done on data adaptation
and content delivery. The work by Lum and Lau discussed
the trade-off between the transcoding overhead and spatial
consumption in content adaptation [16]. CoralCDN, a peerto-
peer CDN, was recently presented; it combines peer-topeer
systems and Web-based content delivery [11]. Chi and
Wu [8] proposed a Data Integrity Service Model (DISM) to
enforce the integrity of data transformed by intermediaries.
In such a model, integrity is enforced by using metadata
expressing modification policies specified by content owners.
However, in DISM, every subject can access the data.
Thus, confidentiality is not enforced. Another problem with
DISM is the lack of efficiency. It does not exploit the
possible parallelism that is inherent in data relationships
and in the access control policies. In several applications
such as multimedia content adaptation [2] efficiency is
crucial. In the partial and preliminary version of this paper
[14], a protocol was proposed to ensure confidentiality and
integrity for XML document updates in distributed and
cooperative systems. In this paper, we present a general and
improved protocol to meet the high availability requirement
for large-scale network services [10].
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 19, NO. 5, MAY 2008 615
. Y. Koglin is with Cisco Systems, RCDN6/3/4, 2200 East President George
Bush Highway, Richardson, TX 75082-3550. E-mail: ykoglin[at]cisco.com.
. D. Yao is with the Department of Computer Science, Rutgers University,
110 Frelinghuysen Road, Piscataway, NJ 08854-8019.
E-mail: danfeng[at]cs.rutgers.edu.
. E. Bertino is with the Department of Computer Science, Purdue
University, 305 N. University Street, West Lafayette, IN 47907-2107.
E-mail: bertino[at]cs.purdue.edu.
Manuscript received 24 Feb. 2006; revised 10 May 2007; accepted 20 June
2007; published online 14 Aug. 2007.
Recommended for acceptance by K. Hwang.
For information on obtaining reprints of this article, please send e-mail to:
tpds[at]computer.org, and reference IEEECS Log Number TPDS-0039-0206.
Digital Object Identifier no. 10.1109/TPDS.2007.70758.
1045-9219/08/$25.00  2008 IEEE Published by the IEEE Computer Society
Our contribution. We summarize our contributions as
follows:
1. We describe the security and content transformation
involved with cache proxies. We present a parallel
secure content service (PSCS) protocol for a cache
proxy and analyze the properties of intermediaries
with caching capacity.
2. We formalize the key management mechanism in
cooperative intermediaries. We introduce the intermediary
profile table for the data server to store
public keys of peer proxies (P-proxies), which are
proxies authorized to perform the same type of data
transformation. Our key management does not
require any preexisting public key infrastructure.
This is possible because the public keys of proxies
are endorsed by the data server in the control
information. Therefore, public-key certificates are
not required in our protocol, even though the
proxies do not need to know each other a priori.
3. We implement our protocol and report the experiment
results on data size, integrity check time, and
servicing time, including the effect of recovery. We
also compare and analyze the performance of our
protocol with a centralized implementation.
4. We describe and analyze the delegation of authorization
among cooperative intermediaries. When an
intermediary is overloaded, our approach makes it
possible for the intermediary to delegate the execution
of content services to another proxy without
violating security requirements. Our delegation
mechanism is simple to implement, yet it largely
improves the availability of proxies.
In our model (see Fig. 1), we distinguish three types of
entities:
1. Data Server. This is an entity that originally stores the
data requested by a client.
2. Client. This is any entity that requests data from a
data server. When a client submits a request, besides
the data it requests, it may also include some content
service requirements, arising from device limitations
and data format limitations [4]. If the client does not
specify any service requirements, a proxy that
represents the client may add these requirements.
Such a proxy may be an edge proxy [5].
3. Intermediary. This is any entity that is allowed by a
data server to provide content services in response to
requests by clients. Intermediaries include caching
proxies and transforming proxies.
Our solution uses standard cryptographic primitives,
including a collision-resistant hash function and digital
signatures. We also design a data structure, called control
information, for the data server to manage proxies and
authorizations. Each participant (intermediary or client)
uses control information for integrity checking and secure
communications. We present an algorithm for generating
control information.
The remainder of this paper is organized as follows:
Section 2 introduces preliminary notions that are needed
throughout the paper. Section 3 describes the PSCS
Protocol, and Section 4 presents the PSCScp protocol for a
cache proxy. The complexity and security analysis is given
in Section 5, and experimental results are presented in
Section 6. We conclude the paper in Section 7.
2 PRELIMINARIES
In this section, we introduce the notions and terminology
used in our paper.
2.1 Content Service Functions and Privileges
Each content service belongs to a service function. The
mapping from a content service to a service function is a
many-to-one mapping. For example, a content service may
compress images with less precision in order to reduce their
size, or a content service may perform media conversion
such as from text to audio or a format change such as from
PDF to HTML. All these services belong to a transcoding
function that changes the data from one format into
another. We summarize the basic content service functions
that intermediaries can perform in Fig. 2, which is an
extension of [17]. We include some important classes of
functions that are related to security services, such as the
function of virus scanning.
To ensure data security, an intermediary must have
certain privileges in order to access the data. Based on a
client request, the data server decides the privileges for each
participating proxy. For example, if a proxy needs to
transcode the data from text to audio, then it needs to have
certain privileges from the data server that authorizes this
proxy to perform this transcoding function. Based on
whether a service function needs to modify the requested
data or not, we identify two types of privileges that allow
intermediaries to perform content service functions: read
and update. The read privilege allows a proxy to read and
store the data. The update privilege allows a proxy to read
and modify the data, as, for example, a proxy needs to have
616 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 19, NO. 5, MAY 2008
Fig. 1. System architecture.
Fig. 2. Functions and corresponding privileges.
this privilege in order to execute a content filtering function.
It subsumes the read privilege. For each content service
function, the corresponding privilege types are listed in
Fig. 2.
2.2 Data Representation
We cast our approach in the framework of XML [9], [22]
because of its widespread use in Web services. XML can be
used to manage data, documents, graphics, and even
multimedia data. Also, XML organizes data according to
hierarchical nested structures, thus facilitating the parallelization.
It organizes data into tagged elements. We define
an atomic element (AE) as either an attribute or an element
including its starting and ending tags. A data segment is a
set of elements to which the same access control policy
applies. That is, if a proxy has a read (or write) privilege
over a segment, the proxy has a read (or write) privilege
over all the elements in the segment. We enforce confidentiality
by allowing a proxy to access only the segments
that are permitted by access control policies. We assume
that each segment is uniquely identified.
Based on the above concepts, we introduce our approach
to data representation as follows:
Let D ¼ fae1; ae2; . . . ; aemg be the data to be transferred,
consisting of a set of AEs. Each AE is identified by an
identifier. Data D are partitioned into a set of segments
fSeg1; Seg2; . . . ; SegKg such that
1. 8i 2 f1; . . .;Kg, Segi ¼ ði; faei1; aei2 ; . . . ; aeirgÞ, each
segment consists of a segment identifier ðiÞ and of a
set of AEs.
2. 8i 2 f1; . . .;Kg and 8j 2 f1; . . . ; rg, ij 2 f1; 2; . . .;mg,
each AE in a segment belongs to D.
3. 8i 2 f1; . . .;Kg, 8k; z 2 f1; . . . ; rg, if k 6¼ z, then
ik 6¼ iz, AEs within the same segment are distinct.
4. 8i, k 2 f1; . . .;Kg and i 6¼ k, Segi \ Segk ¼ ;, AEs
within disjoint segments are distinct.
5. For any aei 2 D, 9j 2 f1; . . .;Kg such that aei 2 Segj,
if an AE aei belongs to D, then aei must belong in a
segment.
Properties 1, 2, and 4 ensure that there are a limited number
of segments for the data. Property 3 ensures that the size of
each segment is minimal. Property 5 ensures that the data is
included in the segments. These properties ensure that the
data is correctly represented by the set of segments.
To enforce authenticity and integrity, we rely on
standard cryptographic primitives such as RSA public keys
for digitally signing the data. Each segment has an
encrypted hash value associated with it. If a proxy has an
update privilege over a segment, when the proxy completes
updating the segment, it generates a hash value by applying
to the segment text, which also includes the segment
identifier, a one-way hash function and then encrypts the
value with its private key. Fig. 3 shows an example of data
segments, which includes the result for virus scan and the
data that is scanned. Attributes delegateKey and delegateHash
are defined in Section 2.3.
2.3 Data Provider (DP) and P-Proxy
A DP is any entity that can provide the data requested by a
client. Thus, a DP may be either a data server or a cache
proxy caching the data requested by clients. In order to
provide content services to clients, a DP has a group of
cooperative intermediaries that can perform different
content services.
AP-proxy is a list (size 1) of proxies that perform certain
content services on the data on behalf of the DP. That is, for a
DP, there may exist more than one cooperative proxy that can
perform certain content services for it. Each DP maintains the
information about the services provided by each cooperative
proxy in an intermediary profile table. The intermediary
profile table stores the public keys and the authorizations of
proxies. Fig. 4 shows an example of such a table.
Because a proxy may provide several content services, it
may appear in several different P-proxies maintained by a
DP. In Fig. 4, proxy1 appears in both P-proxy1 and P-proxy4.
Even though a P-proxy may group several proxies, only
one proxy in such group performs the content service
associated with the P-proxy on each requested data. For
example, suppose that proxy1 is a virus scan proxy in Pproxy1
and that P-proxy1 also includes proxy2. If proxy1 is
overloaded, it can delegate to proxy2 the execution of the
service. We refer to the proxy that is initially assigned to
execute the operation on the data as the primary proxy (prim) of
this P-proxy for the requested data. In the previous example,
even though proxy2 executes the virus scan, the primary
proxy is proxy1. The purpose of P-proxies is therefore to
enhance both the availability and the efficiency of the system.
When a primary proxy p delegates the execution of the
content services to another proxy q, where p and q belong to
the same P-proxy, attributes delegateKey and delegateHash
are required, where delegateKey is q’s public key, and
delegateHash is the digital signature of q signed with its
private key on the digest of processed content. Note that
q’s public key is endorsed by p in p’s signature.
2.4 Access Control System
Each DP has its own security policy related to its data. The
access control system of each DP (Fig. 5) enforces which
proxies and clients can access which data.
The inputs to the access control system include a client’s
request, the security policy and the intermediary profile
table by the DP, and the data store. The access control
system can return three possible access decisions:
1. Deny. This indicates that the DP does not have the
data requested by the client, the client is not allowed
to access the data according to the DP’s policy, or no
intermediaries in the DP’s intermediary profile table
KOGLIN ET AL.: EFFICIENT AND SECURE CONTENT PROCESSING AND DISTRIBUTION BY COOPERATIVE INTERMEDIARIES 617
Fig. 3. Example of data segments.
Fig. 4. Intermediary profile table.
exist or are allowed to transform the data into the
version requested by the client.
2. Empty path. This indicates that the client’s request can
be satisfied without any intermediary’s involvement.
3. Path with ACIS. This indicates that the client’s
request can be satisfied with the involvement of
the P-proxies listed in the returned path. ACIS
denotes access control information structure, which
specifies the privileges over the data for each Pproxy
in the path.
We now provide details concerning paths and ACIS.
A path denotes a content service path and explicitly
defines the order according to which each P-proxy has to
receive the data. That is, a path is a list of P-proxies. Let
P ¼ hP-proxy0; P-proxy1; P-proxy2; . . . ; P-proxyðNþ1Þi be a
path such that
1. P-proxy0 is the DP and P-proxyðNþ1Þ is the client.
2. P-proxyi ði 2 f1; . . .;NgÞ corresponds to a content
service requested by the client.
3. If proxy p 2 P-proxyi ði 2 f1; . . .;NgÞ, then p 2 PT,
where PT is the P-proxy in the DP’s intermediary
profile table that performs the same content service
as P-proxyi. This requirement ensures that only
proxies in the intermediary profile table are allowed
to perform content services on the requested data.
4. If proxy p 2 PT and p is allowed by the DP’s security
policy to perform that content service on the data,
then p 2 P-proxyi.
This requirement ensures that each P-proxy in Path
includes all proxies that can perform that content service
and also satisfy the security policy over the requested data.
Example 1. Suppose the following operations are to be
performed on the requested data: virus scanning, logo
adding, and audio-to-text conversion. The DP has an
intermediary profile table asin Fig. 4,andits security policy
allows these intermediaries to perform content services.
The following content service path can be derived:
hP-proxy0; P-proxy3; P-proxy2; P-proxy1, P-proxy4i which
is illustrated in Fig. 6.Aswill be described in Section 3.1.2, a
proxy (or client) is responsible for the integrity checking of
the proceeding data transformation. Therefore, in Fig. 6, a
cheating Proxy4 or Proxy5 will be detected and corrected
by Proxy3. Note that for audio-to-text conversion, a
malicious proxy may insert arbitrary text into the data.
Because of the nature of the operation, it is very difficult for
the next proxy (or the client) to determine whether the
conversion is done honestly orsomearbitrary text has been
attached. Thedefense against such attack is out of the scope
of this paper and remains an interesting open question.
The requirements for the content service path are that the
path should obey the same segment update-update order
and update-read order. That is, if a segment is updated by
content services i and j, the order of i and j is important.
For example, in the previous example (Fig. 6), if segment
seg is updated by both logo adding and audio-to-text
conversion, then only after audio-to-text conversion can the
logo be added to the segment. Thus, the content service
dealing with text conversion must be placed before logo
adding. Also, as the virus scan needs to read this segment,
the virus scan must be placed after the logo-adding service.
Any content service path that satisfies the security policy
and these order requirements can be used in our approach.
The presence of more than one content service path for a
request will not affect the control information (Section 2.5)
generated for each P-proxy and the client.
Next, we explain the properties of ACIS. Let K be the
total number of segments in the requested data. Let ACIS ¼
har0; . . . ; arN; arðNþ1Þi be the access control information
structure such that
1. ari ¼ ðreadSet; updateSetÞ, where i 2 ½1;N; access
segments for P-proxyi in Path are split into read and
update segment sets.
2. readSet  f1; . . .;Kg, updateSet  f1; . . .;Kg; the
readSet (or updateSet) is a subset of the entire
segments.
3. readSet \ updateSet ¼ ;; if a segment is only readable
for a P-proxy, then it cannot be in the updateSet
of this P-proxy. If a segment is updatable for a Pproxy,
then readability is implied, and there is no
need to include the segment in the readSet.
4. updateSet [ readSet  f1; . . .;Kg; the union of the
sets is a subset of the entire segments.
For example, ar0 is the access information for the DP.
Thus, ar0:readSet ¼ ;, and ar0:updateSet ¼ f1; . . .;Kg.
arðNþ1Þ is the access information for the client. Thus,
arðNþ1Þ:readSet ¼ f1; . . .;Kg, and arðNþ1Þ:updateSet ¼ ;.