Samira Barouti

Feras Aljumah

Dima Alhadidi

Mourad Debbabi

Secure and Privacy-Preserving Querying of Personal Health Records in the Cloud

Personal Health Records (PHR) are user-friendly, online solutions that give patients a way of managing their own health information. Many of the current PHR systems allow storage providers to access patients' data. Recently, architectures of storing PHRs in cloud have been proposed. However, privacy remains a major issue for patients. Consequently, it is a promising method to encrypt PHRs before outsourcing. Encrypting PHRs prevents health organizations from analyzing medical data. In this paper, we propose a protocol that would allow health organizations to produce statistical information about encrypted PHRs stored in the cloud. The protocol depends on two threshold homomorphic cryptosystems: Goldwasser-Micali (GM) and Paillier. It executes queries on Kd-trees that are constructed from encrypted health records. It also prevents patients from inferring what health organizations are concerned about. We experimentally evaluate the performance of the proposed protocol and report on the results of implementation.

Introduction

Electronic health records are usually managed by different healthcare providers including primary care physicians, therapists, hospitals and pharmacies. Consequently, it is difficult to get a single patients history due to the fact that it is spread between multiple providers. It has become a recent trend for patients to take these matters into their own hands by managing their own records using a Personal Health Record (PHR) system. PHRs systems allow patients to manage their medical data, giving them the ability to create, view, edit, or share their medical records with other users in the system as well as with healthcare providers [START_REF] Löhr | Securing the e-health cloud[END_REF]. In the past few years, many providers have created platforms to manage PHRs with features including flexible access control, mobile access, and complex automated diagnoses that analyze PHRs and alert patients when a preventive checkup is needed. These providers include Microsoft HealthVault [START_REF]Microsoft health vault[END_REF] and Dossia [START_REF]Dossia personal health platform[END_REF]. Due to the sensitivity nature of health data, security concerns have prevented many patients from using PHR systems. Many of the providers of the current PHR systems have the ability to access all patient records.

Recently, architectures for storing PHRs in the cloud have been proposed [START_REF] Löhr | Securing the e-health cloud[END_REF]. However, this does not solve the privacy problem and the latter remains an issue for many patients. Since these records are stored on cloud servers, it means that these servers have the ability to read any medical record in the system. In addition, if an attacker is able to compromise a cloud server, then all the PHRs would be exposed. For these reasons, researchers have begun searching for a way to allow patients storing their medical records in the cloud using a Database-as-a-Service (DaaS) model while preserving their privacy. DaaS is a category of cloud computing services that enables IT providers to deliver database functionality as a service. Encrypting PHRs before outsourcing appears to be a promising solution in this domain. However, it prevents health organizations from analyzing medical data for research purposes. To better understand what caused a disease, health organizations and researchers need as much data as possible about the infected patients.

In this paper, we propose a protocol that allows health organizations producing statistical information about encrypted PHRs stored in the cloud. The proposed protocol also does not enable patients to infer about what health organizations are concerned about; not to worry or panic patients targeted by the queries. Intuitively, the proposed protocol works as follows: Patients are organized in small groups. The patients of a given group jointly generate public keys for encryption. They later encrypt their PHRs using their public keys and send the ciphertext to the cloud server. Encrypted records are stored in Kd-trees constructed by the cloud server for each group. To execute SQL queries, Kdtrees are traversed in the cloud server. Finally, the cloud server aggregates the results and sends the final query result to the health organization. However, realizing this seemingly simple system presents a number of significant challenges. First, the search should be performed on encrypted records. To achieve this, our proposed protocol depends on the homomorphic properties of two semanticallysecure encryption schemes. Using homomorphic schemes, specific operations can be performed on the encrypted records directly without the need for decryption. More specifically, query predicates are evaluated using the Goldwasser-Micali (GM) cryptosystem [START_REF] Goldwasser | Probabilistic Encryption & How To Play Mental Poker Keeping Secret All Partial Information[END_REF] and Fischlins protocol [START_REF] Fischlin | A cost-effective pay-per-multiplication comparison method for millionaires[END_REF] whereas query aggregate functions are computed using Paillier cryptosystem [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF]. Second, the engagement of the patients in the protocol execution should be minimal. We achieve this by using threshold cryptosystems such that the decryption process is performed by a specific number of patients, namely the threshold k.

The contributions of our paper can be summarized as follows:

-We propose a protocol, which allows health organizations producing statistical information about PHRs stored in the cloud and encrypted using semantically-secure encryption schemes. The main characteristics of the protocol are the following:

• It preserves the privacy of health organizations and patients.

• It supports aggregate queries such count, sum, max and min. -We design and implement a prototype of the proposed protocol and we also report on the experimental results.

The rest of the paper is organized as follows. Section 2 discusses the execution environment. Section 3 briefly overviews the literature that the proposed solu-tion depends on. Section 4 presents a protocol to find the maximum/minimum value of encrypted inputs without resorting to deterministic encryption schemes. In Section 5, the proposed protocol is presented. The security and complexity analysis of the protocol as well as the experimental results are discussed in Section 6. Section 7 presents the related work. Finally, concluding remarks as well as a discussion of future work are presented in Section 8.

Execution Environment

In this section, we first identify the involved entities. Then, we present the assumptions underlying the system design.

Entities

There are three main entities: (1) Patients who own health records and want to store them on a cloud server while keeping them confidential from the cloud server and health organizations. A common way to protect health records stored on cloud servers is through encryption, (2) Cloud server that stores the encrypted health records of the patients and executes the queries of the health organization over the encrypted records. The cloud server will assign an assisting server to each group. The assisting server is a cloud computing instance, which will be responsible for storing the encrypted records of the patients and executing the SQL queries of the health organization, (3) Health organization that execute queries over the encrypted records of the patients and produce statistical information.

Assumptions

We assume that there is no fully trusted entity in the environment and all entities are semi-honest. Semi-honest adversaries follow the protocol steps, but they try to extract information about other entities' input or output. This is a common security assumption used in secure multiparty computation literature [START_REF] Jiang | A Secure Distributed Framework for Achieving k-Anonymity[END_REF] and it is realistic in our problem scenario since different organizations are collaborating for mutual benefits. Hence, it is reasonable to assume that parties will not Fig. 1: System Architecture deviate from the defined protocol. However, they may be curious to learn additional information from the messages they receive during protocol execution. The cloud server and the assisting servers are modeled as "honest but curious" in the sense that they will execute requests correctly, but they are not reliable to maintain data confidentiality. Regarding query privacy, we assume that the shape of SQL queries submitted by health organizations is public whereas the constants contained in the query predicates are private [START_REF] Olumofin | Privacy-preserving queries over relational databases[END_REF][START_REF] Barouti | Symmetrically-Private Database Search in Cloud Computing[END_REF]. We also assume that there is no collusion between the different parties and that there are mechanisms that ensure integrity and availability of the remotely stored data. Our scheme focuses only on confidentiality and privacy issues and does not provide protection against attacks such as data tampering and denial of service.

Building Blocks

Homomorphic Encryption: It is a form of encryption where a specific algebraic operation performed on the plaintext is equivalent to another (possibly different) algebraic operation performed on the ciphertext. The Paillier's scheme [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF] is an additive homomorphic public key encryption. Using Paillier's scheme, given two ciphertexts E(x) and E(y), an encryption of their sum E(x+y) can be efficiently computed by multiplying the ciphertexts modulo a public key N , i.e., E(x + y) = E(x).E(y) mod N . The Goldwasser-Micali (GM) cryptosystem is a semantically-secure scheme based on the quadratic residuosity problem. It has XOR homomorphic properties, in the sense that E(b) . E(b ) = E(b ⊕ b ) mod N where b and b are bits and N is the public key. Variations of the homomorphic Paillier and GM cryptosystems are the distributed threshold decryption schemes in which the decryption is performed by a group of participants, rather than one party [START_REF] Katz | Threshold Cryptosystems Based on Factoring[END_REF][START_REF] Barnett | Mental Poker Revisited[END_REF]. In this case, each participant would obtain a share of the secret key by executing the distributed key generation algorithm detailed in [START_REF] Boneh | Efficient Generation of Shared RSA Keys[END_REF].

Private Comparison: Yao's classical millionaires' problem [START_REF] Andrew | Protocols for Secure Computations[END_REF] involves two millionaires who wish to know who is richer. However, they do not want to find out inadvertently any additional information about each other's wealth. More formally, given two input values x and y, which are held as private inputs by two parties respectively, the problem is to securely evaluate the Greater Than (GT) condition x > y without exposing inputs. In this paper, we employ Fischlin's protocol [START_REF] Fischlin | A cost-effective pay-per-multiplication comparison method for millionaires[END_REF] for the private comparison because it allows us to compare two ciphertexts encrypted with the GM crytosystem using the same public key. Fischlin's protocol takes as input two ciphertexts encrypted using GM cryptosystem and produces ciphertext sequences, namely ∆ and c that are encrypted by the same public key. The decryption of these sequences would reveal the result of comparing the private inputs without revealing anything beyond the result of the comparison. Fischlin's protocol utilizes the XOR-homomorphic GM cryptosystem to privately compute:

x > y ⇐⇒ n i=1 x i ∧ ¬y i ∧ n j=i+1 (x j = y j ) ⇐⇒ n i=1 x i ∧ ¬y i ∧ n j=i+1 ¬(x i ⊕ y i ) where |x| = |y| = n.
Kd-trees: Kd-trees [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF] are binary trees where the keys differs between levels. Kd-trees are used extensively in searching multidimensional data, in particular database records. The normal way of constructing a balanced Kd-tree is to sort the records according to the i-th attribute and split them into left and right parts, with respect to the median element. The process is then repeated recursively on both parts taking into consideration the (i + 1)th attribute.

Secure Maximum/Minimum Computation

As a major step in our proposed protocol, we need to execute the max /min aggregate queries over encrypted records. In this section, we provide a cloud-based solution that calculates the maximum/minimum of encrypted values owned by some parties. Formally, given n inputs v 1 , . . . , v n owned by the parties P 1 , . . . , P n respectively, the cloud server wishes to securely compute max (v 1 , v 2 , . . . , v n ) and min(v 1 , v 2 , . . . , v n ). We assume that the parties are not malicious and they correctly carry out the prescribed steps. The proposed cloud-based solution relies on Fischlin's protocol [START_REF] Fischlin | A cost-effective pay-per-multiplication comparison method for millionaires[END_REF] and the threshold GM cryptosystem [START_REF] Katz | Threshold Cryptosystems Based on Factoring[END_REF]. We explain the technique to find the max but it can be easily modified to find the min.

Parties jointly generate the public key pk for k-out-of-n threshold GM cryptosystem such that at least k patients are required to fully decrypt a ciphertext [START_REF] Katz | Threshold Cryptosystems Based on Factoring[END_REF]. Parties then encrypt their values and outsource them to the cloud server. The cloud server initializes the current maximum to the encryption of a small negative value with the threshold GM cryptosystem. Afterwards, the cloud compares the current maximum with the encrypted value of the party P i using Fischlin's protocol. The outputs of Fischlin's protocol are sequences of λ elements. To decide whether the encrypted value of P i is greater than the current maximum (If there exists a sequence of λ quadratic residues), the cloud server contacts k other parties and sends the generated sequences for them. Each party performs calculation on the sequences using her share of the factors of the public key [START_REF] Katz | Threshold Cryptosystems Based on Factoring[END_REF] using the threshold GM decryption. The results are then submitted to the cloud server. Afterwards, the cloud server combines the results received from k parties and decide if the encrypted value of P i is greater than the current maximum based on the quadratic residuosity of the combinations. If the output indicates that the current maximum is greater, there is no need to update the current maximum. Otherwise, the cloud server sets the current maximum to the value of P i and repeats the same process with P i+1 . After comparing the current maximum with all the existing values, the cloud server sends the encrypted maximum value to k members for decryption. This idea can be extended to enable a cloud server to sort the encrypted values without knowing the secret key and the plaintexts. In this case, any comparison-based sorting algorithm can be utilized and the comparison is performed on the encrypted values by exploiting Fischlin's protocol.

Secure Execution of Health Queries in Cloud

In this section, we present a protocol that enables health organizations to produce statistical information about encrypted personal health records stored in the cloud server. The proposed protocol prevents patients from inferring what health organizations are concerned about. The health organization's input is an aggregate SQL query that consists of exact-matching and intervalmatching predicates over multiple attributes combined with logical operators (AND/OR/NOT). The cloud server's input is the encrypted health records of the patients. The naive approach to achieve these objectives is that the health organization communicates with each patient and securely evaluates queries on her record. This can be achieved by exploiting Fischlin's protocol for private comparison. However, this approach incurs excessive communication and computation overhead on the health organization side that is linear to the number of patients.

To reduce this overhead, patients are organized into smaller groups. The patients in each group jointly generate two public keys for Goldwasser-Micali [START_REF] Goldwasser | Probabilistic Encryption & How To Play Mental Poker Keeping Secret All Partial Information[END_REF] and Paillier [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF] encryption schemes. Then, they encrypt their records and outsource them to the cloud server for storage. The cloud server assigns an assisting server to each group. Assisting servers are responsible for securely executing health organization's queries on the database of each group to obtain partial results. Assisting servers then collaborate to combine the partial results into the query result and report it to the health organization. In the following, we elaborate the basic steps of our protocol that protects the data privacy of patients and the query privacy of the health organization.

Key Generation and Tree Construction

Assuming the total number of N patients, the cloud server defines L = √ N groups. It then randomly maps and assigns each patient into exactly one group. Let n = N L denotes the number of patients in each group. The cloud server assigns an assisting server to each group, which is responsible for executing health organizations' queries over the medical database of patients. Assisting servers collaborate with each other to obtain the query result from the partial results and send it to the health organization. In the i-th group, the patients execute the distributed key generation algorithms for the threshold Paillier and the threshold GM cryptosystems to obtain the public keys pk i and pk i for Paillier and GM cryptosystems. We utilize the protocols explained in [START_REF] Katz | Threshold Cryptosystems Based on Factoring[END_REF] and [START_REF] Nishide | Distributed Paillier Cryptosystem Without Trusted Dealer[END_REF] for the threshold GM and the threshold Paillier cryptosystems, respectively. These protocols depend on distributed RSA key-generation protocols [START_REF] Frankel | Robust Efficient Distributed RSA-Key Generation[END_REF][START_REF] Boneh | Efficient Generation of Shared RSA Keys[END_REF] without the need to a trusted dealer. Following the execution of the key-generation protocols, each patient obtains a single public key and a share of the secret key. The threshold cryptosystems enable the patients to encrypt their record with a single public key while at least a minimal number of patients are required to decrypt a ciphertext.

Example 1. Consider health records with the attributes Age and Surgery, where the value of Surgery specifies the type of the surgery that a patient undergoes (e.g. 1: Transgender, 2: Plastic, 3:Vascular, 4: Urology). The total number of patients is N = 10; therefore, these patients are organized in L = √ 10 = 3 groups, namely, G 1 , G 2 and G 3 . Assume that patients 1,9 and 10 are assigned to G 1 ; patients 2, 4, 5 and 8 to G 2 and patients 3, 6 and 7 to G 3 , randomly. Furthermore, the patients in the group G i jointly generate the public key pk i and pk i for the GM and the Paillier cryptosystems, respectively. The members of G i encrypt their records with pk i and pk i as presented in Fig. 2. The encrypted tables are then outsourced to the cloud server.

To store the shares of a secret key, we assume the secret key is stored on secure hardware such as FPGA [START_REF] Eguro | FPGAs for Trusted Cloud Computing[END_REF]. These devices are designed in such a way that after a patient places a key into the on-board key memory on the device, it cannot be read externally. After the secret key of each patient and the group public keys (for Paillier and GM cryptosystems) have been written, the FPGA can be delivered to the cloud operator for installation.

AgeGM SurgeryGM AgeP SurgeryP Patient 1 E pk 1 (34) E pk 1 (1) E pk 1 (34) E pk 1 (1) Patient 9 E pk 1 (83) E pk 1 (3) E pk 1 (83) E pk 1 (3) Patient 10 E pk 1 (42) E pk 1 (3) E pk 1 (42) E pk 1 (3) (a) G1 Data set AgeGM SurgeryGM AgeP SurgeryP Patient 2 E pk 2 (39) E pk 2 (2) E pk 2 (39) E pk 2 (2) Patient 4 E pk 2 (59) E pk 2 (3) E pk 2 (59) E pk 2 (3) Patient 5 E pk 2 (63) E pk 2 (4) E pk 2 (63) E pk 2 (4) Patient 8 E pk 2 (11) E pk 2 (2) E pk 2 (11) E pk 2 (2) (b) G2 Data set AgeGM SurgeryGM AgeP SurgeryP Patient 3 E pk 3 (20) E pk 3 (1) E pk 3 (20) E pk 3 (1) Patient 6 E pk 3 (27) E pk 3 (2) E pk 3 (27) E pk 3 (2) Patient 7 E pk 3 (78) E pk 3 (4) E pk 3 (78) E pk 3 (4) (c) G3 Data set

Fig. 2: Outsourced Health Records in Groups

The patients encrypt each record using both Paillier and GM cryptosystems by the group public keys. Therefore, the encrypted record of each patient has two columns for each attribute in the database: one column that contains the encryption of the attribute value using the group public key for the threshold Paillier cryptosystem, and another column that stores the GM encryption of the attribute value using the group public key for the threshold GM cryptosystem. Finally, the cloud server assigns an assisting server to each group. Each assisting server collects the encrypted health records and organizes them as a Kd-tree, as described in Section 3.

Example 2. (Continued from Example 1)

The generated Kd-trees for each group are shown in Fig. 3. The partitioning attributes in each group may be different.

Epk 1 Ô42Õ Epk 1 Ô3Õ Epk 1 Ô34Õ Epk 1 Ô1Õ Epk 1 Ô83Õ Epk 1 Ô3Õ Age (a) G1 Kd-tree Epk 2 Ô59Õ Epk 2 Ô3Õ Epk 2 Ô39Õ Epk 2 Ô2Õ Epk 2 Ô11Õ Epk 2 Ô2Õ Epk 2 Ô63Õ Epk 2 Ô4Õ
Age Surgery (b) G2 Kd-tree

Epk 3 Ô27Õ Epk 3 Ô2Õ Epk 3 Ô20Õ Epk 3 Ô1Õ Epk 3 Ô78Õ Epk 3 Ô4Õ

Surgery

(c) G3 Kd-tree Fig. 3: Generated Kd-trees

Query Sanitization and Token Generation

The health organization wishes to execute an SQL query such that the constants in the predicates are not revealed to the patients and the cloud server. Therefore, the health organization sanitizes the query by replacing the constants contained in the predicates by their GM encryption using the public key of each group. Furthermore, the health organization uses a token for each group that is encrypted by the group's public key. This token can be manipulated by assisting servers to produce a noisy query result. Generating the token depends on the type of the aggregate function. For count and sum, the health organization generates L random numbers R 1 , R 2 , . . . , R L such that R = R 1 + R 2 + . . . + R L . The random share R i will be the token that is sent to the assisting server of the i-th group.

For the max and min, the health organization generates a random number R as the token for all groups. The health organization then encrypts the token of each group by the Paillier cryptosystem using the group public key. The health organization forwards the sanitized query together with the encrypted token to assisting servers. Therefore, in this step the health organization should create L sanitized queries and L encrypted tokens.

Example 3. Suppose that the health organization's query is:

SELECT MAX(Age) FROM D WHERE Surgery = 1
The sanitized query that will be forwarded to the i-th group would be

SELECT MAX(Age) FROM D WHERE Surgery = E pk i (1)
In addition, since the function is max, the health organization generates a random number R and uses it as the token for all groups. The health organization then encrypts the token using the Paillier encryption by the public key of each group and forwards the encrypted token together with the sanitized query to the corresponding assisting server.

Tree Traversal and Query Execution

To execute the health organization's query, the assisting servers must traverse the Kd-trees, constructed from the encrypted records of the patients. To do so, the assisting servers follow the tree traversal algorithm. The search begins from the root; the assisting server uses Fischlin's protocol and the threshold GM decryption to evaluate the query predicate on the root record. Based on the result of the query evaluation, the search is continued on the left tree or the right subtree or both. At the end of this step, the assisting servers will end up with the records that satisfy the query predicate. The assisting servers then compute the encrypted query result depending on the type of the aggregate function as follows:

count: The assisting server of the group G i counts the number of records that are reported as the query result and encrypts this value using the Paillier cryptosystem with the group public key. sum: The assisting servers encrypt 0 (as the current sum) by the Paillier encryption using the group public key. While traversing the tree, if at each level the conditions in the query predicate are satisfied, the assisting server projects the record over the Paillier-encrypted column targeted by the aggregate function and multiplies it by the the current sum to update the query result. At the end, the assisting server will end up with the sum that is encrypted with the group public key using the threshold Paillier cryptosystem. max, min: Initially, the assisting servers pick up a small negative number (or a large positive in case of min) that denotes the current max/min value and encrypts it by the GM and the Paillier cryptosystems using the group public keys. GM-encrypted ciphertext is utilized for the comparison while Paillierencrypted ciphertext is used for generating noisy query result. During the tree traversal if a record satisfies the query condition(s), the assisting server projects the record over the columns that contain the GM-and the Paillierencryption of the record. It then executes Fischlin's protocol using the encrypted current max/min value and the GM-encrypted value, to find out if this record has greater (resp. smaller) value or not. If so, the assisting server initializes the current max/min value to the GM-and the Paillier-encrypted ciphertexts. Otherwise, the current max/min value remains unchanged. At the end, the assisting servers end up with the query result encrypted with the Paillier and GM cryptosystems. For the remaining step of the protocol, the assisting servers only need the Paillier-encrypted ciphertext.

At the end of this step, the assisting servers obtain the partial query result (that has been encrypted using the Paillier scheme by the public key of the group). All assisting servers receive an encrypted token E pk i (R) from the health organization. The assisting server of the group G i extracts E pki (1) from the query and performs the point search on the Kd-tree constructed by the patients in the group G i . The assisting servers report the records that satisfy the predicate Surgery = E pki (1) by executing Fischlin's protocol and the threshold GM cryptosystem. The record of Patient 1 in G 1 and the record of Patient 3 in G 3 satisfy the predicate. Therefore, the output of the tree traversal for the assisting servers of the groups G 1 , G 2 and G 3 will be {E pk1 (34), E pk 1 (34)}, {E pk2 (-1000), E pk 2 (-1000)} and {E pk3 [START_REF] Dwork | Differential Privacy: A Survey of Results[END_REF], E pk 3 (20)}, respectively. The resulted outputs will be projected over the column Age P to obtain {E pk 1 (34)}, {E pk 2 (-1000)} and {E pk 3 (20)} as the encrypted query result.

Query Result Decryption

So far, the assisting servers have obtained the encrypted partial query result, which we will call group results from now on. Therefore, the assisting servers must collaborate with each other to compute the final query result and submit it to the health organization. The group results are encrypted with different keys. Therefore, in order to compute the final query result, the group results must be in plaintext. The assisting servers first obfuscate the group results because they are not willing to reveal these results to each other. The obfuscation is performed by the mean of multiplying the group result by the encrypted token, sent by the health organization (both of them are ciphertexts generated by the same key under the Paillier cryptosystem). The obfuscation allows the assisting servers to collaborate with each other to calculate the noisy query result while hiding the actual group result. In addition, since the noise is generated by the health organization, it allows the health organization to recover the actual query result from the noisy query result. Afterwards, each assisting server decrypts the noisy group result that is encrypted by the Paillier cryptosystem by contacting patients in its group. The assisting servers then need to obtain the final noisy query result by aggregating their group results. In this context, the assisting servers send the noisy group results in plaintext to the cloud server. The cloud server then aggregates the partial noisy query results to obtain the noisy query result. In the case of count and sum, the cloud server adds up all the group results and submits the summation to the health organization. In the case of max and min aggregate functions, the cloud server executes the maximum/minimum algorithm on the plaintexts and sends the resulted value to the health organization. Notice that the noise generated for obfuscating the maximum/minimum of all groups is the same, therefore it will not affect the algorithm correctness (i.e., if a < b then a + R < b + R). Finally, the health organization in its turn subtracts the noise and obtains the query result. on the groups G 1 , G 2 and G 3 was {E pk 1 (34)}, {E pk 2 (-1000)} and {E pk 3 (20)} respectively. Moreover, the token sent by the health organization to the i-th group is E pk i (R). The assisting servers multiply the received token E R pk i by all records in the encrypted query result to obtain the encrypted noisy query result, i.e., {E pk 1 (34 + R)}, {E pk 2 (-1000 + R)} and {E pk 3 (20 + R)}. The assisting servers then decrypt these ciphertexts to obtain 34 + R, -1000 + R and 20 + R. They send their noisy plaintexts to the cloud server. The cloud server executes the maximum algorithm on the 34 + R, -1000 + R and 20 + R and eventually ends up with 34 + R as the maximum. The cloud server forwards 34 + R to the health organization. The health organization subtracts the noise R to obtain 34 as the result of executing the SQL query on the medical database.

6 Security & Efficiency Analysis

Security Analysis

Assuming the semi-honest adversary model and no collusion between the patients, the security of the protocol depends on the steps where the parties exchange information and it is conducted as follows:

-Health organization-Cloud server : The health organization sends the sanitized query and the token that are encrypted by the semantically-secure encryption schemes using patients' public keys. Therefore, the cloud server is not able to decrypt it [START_REF] Goldwasser | Probabilistic Encryption & How To Play Mental Poker Keeping Secret All Partial Information[END_REF][START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF]. -Patient-Cloud server. The patients sends their medical records, encrypted using semantically-secure encryption schemes that are secure against semihonest adversary [START_REF] Goldwasser | Probabilistic Encryption & How To Play Mental Poker Keeping Secret All Partial Information[END_REF][START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF]. -Cloud server-Patient. The cloud server communicates with the patients in order to execute Fischlin's protocol, that is proven to be secure in the presence of semi-honest adversaries [START_REF] Fischlin | A cost-effective pay-per-multiplication comparison method for millionaires[END_REF][START_REF] Katz | Threshold Cryptosystems Based on Factoring[END_REF][START_REF] Barnett | Mental Poker Revisited[END_REF]. -Assisting servers. The interactions between assisting servers are required to aggregate the noisy group results and acquire the randomized final query result. Since the query results have been randomized by a number that is generated by the health organization, the assisting servers are not able to extract the actual query results from the noisy results.

Moreover, the output of each subprotocol is the input to another subprototcol. Therefore, according to the Composition Theorem [START_REF] Goldreich | Foundations of Cryptography[END_REF], the entire protocol is secure. The main concern with threshold cryptosystems comes from the collusion attack. We address in the following the possible attacks resulted from the collusion between the different parties. The threshold decryption will be compromised if the number of colluding clients under the control of an adversary exceeds the threshold k. Any collusion that contains less than k patients in each group cannot learn any information about the ciphertext sequences ∆ and c, generated for comparison as well as constants in the query of the health organization. The most serious collusion attacks are when: (i) the cloud server colludes with more than k patients in each group to recover the encrypted database records, (ii) the cloud server and at least k patients in any group collude to infer constants in the query. In practice, we can increase the threshold k such that attackers will not be able to compromise too many patients. Despite simplicity, this mechanism has

Health Organization Assisting Servers Communication Computation Communication Computation

O( √ N ) O(k √ N ) O(kT (N )) O(kT (N ))
Table 2: Communication and Computation Cost two disadvantages: First, the number of the required online patients is increased.

Second, the communication cost on the assisting servers is increased because they need to communicate with more parties for decryption. Therefore, there should be a trade-off between availability/efficiency and security by choosing a proper value for k.

It should be noted that the proposed protocol does not protect the privacy of patients from being identified through the query result. There is a significant body of works on distributed privacy preserving data mining (e.g. constructing decision trees [START_REF] Lindell | Privacy Preserving Data Mining[END_REF] and differential privacy [START_REF] Dwork | Differential Privacy: A Survey of Results[END_REF][START_REF] Frank | Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis[END_REF][START_REF] Roy | Airavat: Security and Privacy for MapReduce[END_REF]) that provide a rich and useful set of tools to protect the record owner (i.e., patients) from being identified through query results. They allow a trusted server to release obfuscated answers to aggregate queries to avoid leaking information about any specific record in the database. Such works have a different goal and model and can be added as a front end in the proposed protocol to provide privacy-preserving answers to the health organization's queries.

Complexity Analysis

Let N denotes the number of patients in a PHR system. These patients are organized into L groups and each group contains n = N L patients. Recall that the execution time of range queries, exact matching queries and partial matching queries on a Kd-tree with √ N records, will be O(N 0.5-1/2d + m), O(log N ) and O(N 0.5-s/2d + m), respectively [START_REF] Berg | Computational Geometry: Algorithms and Applications[END_REF] where d is the number of the attributes in the table, s is the number of attributes in the query predicate and m denotes the number of records, reported as the query result. The communication and the computation cost of the protocol is summarized in Table 2 where T (N ) indicates the execution time of different types of queries (e.g., exact-matching, partial matching and range matching). The most communication-and computationintensive operation on the assisting servers is the tree traversal.

Performance Evaluation

To evaluate the performance of the proposed protocol, we implement a prototype relying on some existing open source projects [START_REF] Joakim | Cryptographic Protocols:: Theory and Implementation[END_REF] in Java 1.6. The secret keys p and q of the GM cryptosystem are 256-bit long. Moreover, we employ the publicly available Breast Cancer dataset [START_REF]Breast Cancer Data Set[END_REF]. It has 286 records with 9 categorical attributes. The patient's and the server's side experiments are conducted on an Intel core i5 2.3GHz notebook with 4GB of RAM. The number of patients in each group is fixed at L = 286 leading to approximately 81, 800 patients in the PHR system. The shares of the secret key are stored on FPGAs. Decrypting a ciphertext by the cloud server is performed by sending a ciphertext to the FPGAs. Since the communication is intra-site, we ignore communication delays in the performance evaluation.

To understand the source of the overhead, we measure the query execution time for different types of aggregate SQL queries, but running with only one core enabled. The result is presented in Table 3 and Fig. 4. When k is small, the query time is dominated by Fischlin's protocol, which is independent from the threshold k. Therefore, there is a small difference in the query time when k = 36 and k = 71. However, as k increases the effect of the threshold decryption becomes more visible and the execution time starts to grow. According to a similar analysis, for small values of k there is a small change in the execution time but as k increases the query time becomes linear with k. Finally, we calculate the execution time of an arbitrary SQL query k = n 4 = 71. In addition, the execution time of a query heavily depends on the number of comparisons that are performed to traverse the Kd-tree. Therefore, we consider three different scenarios: (1) the worst case scenario is when evaluating predicates targeting a single attribute for interval matching such that all the tree nodes are traversed, (2) the best case scenario is when evaluating predicates targeting all attributes for exact matching, and (3) the real-world scenario is when evaluating predicates targeting multiple attributes for range and exact matching predicates. In the worst case, the time required to evaluate the predicate is 110 seconds (approximately 2 minutes) for each group, whereas in the best case it is 0.3 seconds. In the real-world scenario, we derive the execution time of a SQL query that contains interval matching and exact matching predicates. For each type of predicate, we execute four SQL queries with different number of attributes. The results are presented in Fig. 5. The results indicate that as the number of attributes in the query increases, the execution time decreases due to the smaller search space and the reduction of the number of comparisons. Our experimental results indicate that the proposed protocol would work well with medium size databases (with a total number of 100,000-400,000 patients) and the queries that contain multiple attributes. These results are from a straightforward implementation of the proposed protocol. Further optimizations may lead to a better performance. It is worth to mention that health organizations do not frequently conduct statistical studies on the medical databases (every month or when there is a pandemic). Therefore, the performance of the protocol is acceptable for this type of applications whose goal is to perform search while the absolute privacy of the patients and the health organization is preserved. 7 Related Work

Private database outsourcing deals with the problem of hiding database records from an untrusted service provider. To ensure the security and privacy of the data stored in the cloud, most existing approaches rely on encryption [START_REF] Sion | Secure data outsourcing[END_REF]. However, using cryptography as a means to protect privacy causes new problems, such as querying the encrypted data. Previous work in querying encrypted data is divided into two categories, one that assumes the existence of a trusted server [START_REF] Iyer | A framework for efficient storage security in rdbms[END_REF], and another that assumes that the server is semi-trusted [START_REF] Hacigümüş | Efficient execution of aggregation queries over encrypted relational databases[END_REF][START_REF] Agrawal | Order preserving encryption for numeric data[END_REF].Hacigumus et al. [START_REF] Hacigümüş | Efficient execution of aggregation queries over encrypted relational databases[END_REF] suggested the addition of secure indexes in each tuple. Although these techniques have been proposed to secure databases hosted in the cloud, they cannot be adopted for this problem for several reasons. First, to evaluate the query on the encrypted data, the health organization must encrypt the query by the same scheme and the same key that are used by the patients and send it to the cloud server. It then forwards the encrypted query to the patients, where the query can be decrypted by the encryption key. Second, a common approach in the existing research proposals is to send a set of encrypted records to the client for filtration and further processing [START_REF] Hacigümüş | Efficient execution of aggregation queries over encrypted relational databases[END_REF][START_REF] Hore | A privacy-preserving index for range queries[END_REF]. Therefore, the cloud server may reveal extra information beyond the query result to the client. Thus, the proposed techniques for secure database outsourcing will not protect the query privacy and the database privacy. Recently, CryptDB [START_REF] Popa | CryptDB : Protecting confidentiality with encrypted query processing[END_REF] has been proposed to execute SQL queries over encrypted data. It depends on a fully trusted component that maintains all the secret and public keys and transforms the users' SQL queries to ones that can be executed over encrypted records. CryptDB has low overhead on query execution time; however, it requires a fully trusted component which is the single point of attack.

Conclusion

In this paper, we have presented a protocol that allows executing various types of SQL queries on PHRs stored in the cloud while preserving the privacy of the patients and the health organization as well. The health records are encrypted using probabilistic encryption schemes, which are semantically secure. The protocol supports aggregate, exact matching and range matching queries. It is based on Fischlin's protocol for private comparison and on two threshold cryptosystems. The implementation result has indicated that the protocol works well with medium size databases and the queries that contain multiple attributes. We have shown that we can execute queries over encrypted data using probabilistic cryptosystems. This opens the door for more research for efficiency in this domain.

Example 4 .

 4 (Continued from Example 3) Considering the Kd-trees presented in Fig. 3 and the sanitized query SELECT MAX(Age) FROM D WHERE Surgery = E pki (1)

Example 5 .

 5 (Continued from Example 4) We have seen that the result of executing the SQL query SELECT MAX(Age) FROM D WHERE Surgery = 1

Fig. 5 :

 5 Fig. 4: Query Time

Table 1 :

 1 Health Records

		Age Surgery
	Patient 1	34	1
	Patient 2	39	2
	Patient 3	20	1
	Patient 4	59	3
	Patient 5	63	4
	Patient 6	27	2
	Patient 7	78	4
	Patient 8	11	2
	Patient 9	83	3
	Patient 10	42	3

Table 3 :

 3 Assisting server latency for different types of SQL queries (k = n 4 = 71).


Chu Huang

Sencun Zhu
email: szhu@cse.psu.edu

Robert Erbacher
email: robert.f.erbacher.civ@mail.mil

Toward Software Diversity in Heterogeneous Networked Systems

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

With the fast advancement of nowadays information technology, organizations are becoming ever more dependent on interconnected systems for carrying on everyday tasks. However, the pervasive interdependence of such infrastructure increases the risk of being attacked and thus poses numerous challenges to system security. One major problem for such networked environments is software monoculture [START_REF] Lala | It monoculture security risks and defenses[END_REF][START_REF] Stamp | Risks of monoculture[END_REF]-running on the risk of exposing a weakness that is common to all of its components, it facilitates the spread of attacks and enables large-scale exploitations that could easily result in overall crash. Considering the consequences of software monoculture in intensively connected systems, there is an urgent need to control the damage of automated attacks that takes advantage of the connectivity of the networked system.

In contrast to homogeneous systems by software monoculture, heterogeneous architectures are expected to have higher survivability [START_REF] Zhang | Heterogeneous networking: a new survivability paradigm[END_REF][START_REF] Yang | Improving sensor network immunity under worm attacks: a software diversity approach[END_REF][START_REF] O'donnell | On achieving software diversity for improved network security using distributed coloring algorithms[END_REF]. This point is very much like the maintenance of genetic and ecosystem diversity in biology. The variability in the biological world allows at least a portion of species to survive an epidemic. Inspired by such phenomena of biodiversity, a good number of techniques have been proposed to improve system resilience and survivability under attacks. However, previous approaches cannot fully meet two highly desired requirements: (R1) Resistance against automated attacks in a networked environment; (R2) Practicability of the solutions under real-world constraints. To see how existing approaches are limited in meeting these three requirements, we classify them into three main categories: software diversity at the system level, software diversity at network level and N-version programming 1) Diversity at the system level is achieved mainly through randomization techniques, which are limited to individual machines and it is not clear if and how they can be extended to improve the survivability of the networked systems as a whole.

2) Diversification methods at the network level compensate the limitations of the former approach, but it suffers from the problem of only considering assignment of one piece of software. In the real world scenarios, however, a host (i.e., a commodity PC) typically is required to install with more than one software (i.e., operating system, web browser, email client, office suite applications etc.) to perform particular tasks. 3) N-version programming: achieves higher system survivability depending on its underlying multiple-version software units that tolerate software faults. This method has very high computational cost and is not practical enough to be used routinely in real-world organizations. 4) Real world deployment constraints have not been formally incorporated into system design in prior research.

In this study we propose a software diversity-based approach to address the problem of survivability in the complex networked systems under automated attacks, with the goal to meet all the design requirements. First, by assigning appropriate software to hosts considering the network connectivity, our approach enhances the system's resistance to automated attacks. Second, our algorithm considers the real-world constraints on resource allocation, which makes it more practical from implementation point of view. We also demonstrate via simulations that the assignment solution generated by our algorithm is better than previous assigning methods, and very close to the optimal solution. Through experiments we found that the level of heterogeneity in our algorithm depends on the ratio of the number of software installed to the total number of available software, and we also identified critical ratio points for different representative topologies. The capability and possibility of our algorithm in creating moving target defense are also evaluated. Our findings may give some guidelines for choosing appropriate system parameters for balancing the trade-off between survivability and cost. Take the graph in Fig. 1 as an example. There are 11 machines represented by nodes and 5 distinct software products represented by different colors. We expect diverse software products developed by different people will not have the same vulnerability for the attacker to exploit [START_REF] Han | On the effectiveness of software diversity: A systematic study on real-world vulnerabilities[END_REF], and an attack can propagate from one node to another by exploring one kind of vulnerabilities residing in a particular software product. By applying our algorithm on this graph, we find that even in the worst-case scenario a successful attack can only compromise four machines (in green) at most. This indicates that by optimally assigning software to connected machines in a non-adjacent manner, our algorithm can effectively reduce the epidemic effect of an attack.

Related Work

Software Diversity The state-of-the-art approaches on software diversity are classified into three main categories: diversity at the system level and the network level, and N-version programming.

Software diversity at the system level has been researched to address space layout randomization, instruction set randomization and data randomization. Address space layout randomization (ASLR) [START_REF] Snow | Just-in-time code reuse: On the effectiveness of fine-grained address space layout randomization[END_REF] randomizes the memory address of the program region and has already been implemented in major operating systems [START_REF] Giuffrida | Enhanced operating system security through efficient and fine-grained address space randomization[END_REF]. The instruction set randomization (ISR) [START_REF] Davi | Gadge me if you can: secure and efficient ad-hoc instruction-level randomization for x86 and arm[END_REF] obfuscates underlying system's instructions in order to defeat code-injection attacks. Data randomization [START_REF] Philippaerts | Code pointer masking: hardening applications against code injection attacks[END_REF] is another randomized-based approach, which applies masks on data in the memory, so that the attacker cannot determine memory regions that are associated with particular objects. Diversity at the network level is achieved by using different applications [START_REF] Yang | Improving sensor network immunity under worm attacks: a software diversity approach[END_REF] [5], operating systems, and shuffling techniques within a networked system [START_REF] Jafarian | Openflow random host mutation: transparent moving target defense using software defined networking[END_REF]. N-version programming was introduced in the 1970s which depends on functionally equivalent versions of the same program and monitors the behavior of the variants in order to detect divergence of the results [START_REF] Salamat | Orchestra: intrusion detection using parallel execution and monitoring of program variants in user-space[END_REF].

Graph Coloring Graph coloring [START_REF] Jensen | Graph coloring problems[END_REF] is a famous problem in graph theory, which ensures there is no two adjacent nodes sharing the same color. Its solutions is a natural option in modeling a wide range of real-life problem for making globally optional decision [14] [4]. In most cases, however, the basic graph coloring problem fails to model some real-life problems where additional constraints have to be satisfied. Variants of the basic coloring problem have been introduced and intensively studied which allow one to take into account certain local constraints. List coloring [START_REF] Voigt | List colourings of planar graphs[END_REF], precoloring extension [START_REF] Hujter | Precoloring extension. ii. graph classes related to bipartite graphs[END_REF] and H-coloring [START_REF] Bulatov | H-coloring dichotomy revisited[END_REF] are examples of local constraints. In some cases, these problem can be more difficult algorithmically than traditional vertex coloring [START_REF] Hujter | Precoloring extension. ii. graph classes related to bipartite graphs[END_REF] [START_REF] Tuza | Graph colorings with local constraints-a survey[END_REF]. Another widely studied coloring problem is multicoloring problem [START_REF] Borodin | On sum coloring and sum multi-coloring for restricted families of graphs[END_REF] where more than one color have to be assigned to each vertex. Despite the rich literature, none of the existing coloring algorithms works under our constraints.

3 Problem Formulation

System Model

In this work, we use an undirected graph as the abstraction of a general finite networked system. Formal definition of the graph is given as follows.

Definition 1 (Communication Graph) A communication graph is an undirected graph G = (V, E), where V is a finite set of nodes which represents hosts and devices comprising the networked system, and E as a set of edges represents the communication links (e.g., physically directly connected or can communicate through network e.g. using TCP/UDP) between two nodes.

Example networked systems include intranet, enterprise social networks, tactical mobile ad hoc networks, wireless sensor networks of different network topologies. We show an example of how to model a real-world network using communication graph of nodes and edges (Fig. 2). In this example, we have three servers reside in the DMZ, seven workstations and a database server located in the internal network. The links shown between workstations and servers depict direct communication between them. Corresponding communication graph of the network can then be generated based on their connectivity.

Considering the characteristics of the system model, edges of the communication graph can be classified into two types of links: defective edge and immune edge. Defective edge is a type of connection whose two endpoints have the same type of software installed (hence potentially share the same types of vulnerabilities. Note that our algorithm does not assume the knowledge of vulnerabilities. We discuss this more in Section 6). Otherwise, an edge is an immune edge. In this paper, based on the above definitions, we further define formally the concept of common vulnerability graph.

Definition 2 (Common Vulnerability Graph): A common vulnerability graph (CVG) S is a subgraph of a communication graph G, inside which all vertices share a common software and are connected through defective edges, whereas all its boundary edges are immune edges.

Graph Multi-Coloring Problem with Local Constraints

Using the model described earlier, we model the software assigning problem as a graph multi-coloring problem, where each machine is represented by a vertex and each distinct software product is represented by a color. In the multi-coloring problem each node has a demand w(v i ), which is the number of colors it requires. We further define G = (V, E, W ) to be a weighted communication graph with a weight vector W which denotes the number of software required for vertices V of the graph. A multi-coloring task of G is an assignment of colors to the vertices such that each vertex v i is assigned with w(v i ) colors in a way that two connected node cannot be assigned same colors.

However, practical software assignment contains several implicit constraints which basic multi-coloring problem fails to capture. For our work, we specifically consider two types of constraints that give rise to different system requirements, as defined below.

Definition 3 (Constraint): If a single host or a pair of hosts is restricted by some pre-defined software assigning rules, we say that the host(s) is/are constrained.

-Host constraint: certain hosts must be installed with some specified types of software to perform required functionality (e.g., to deploy a database server it is required to assign DB2); -Software constraint: certain combination of software must or must not be assigned to specified hosts simultaneously (e.g., PHP, Apache, MySQL and Linux need to be assigned together to implement LAMP on a single node).

We note that these practical requirements could lead to the potential danger that nodes with the same software are neighbors, which violates the coloring rule that adjacent vertices have different colors. To better sketch our problem, we relax the requirement and re-define a less restrictive coloring rule that allows neighboring vertices to receive the same colors. The only thing we require is that the resulting CVG by that color has to be as small as possible. According to the definition, a defective edge indicates that the exploitation of one type of vulnerability on one host could lead to the compromise of its neighboring host following this "path" while immune edge naturally stops propagation of such automated attack. Thus we can use the size of CVG to indicate the infection range of an automated attack (e.g., worm attack). If one can effectively limit the size of the CVG, system survivability can then be improved. Throughout the present paper, we denote the size of the largest size of the CVG as S, indicating the worst-case infection scenario. The ideal case is when every node in the network is isolated as a single CVG with size one (i.e. no defective edge). Hence, our ultimate research question becomes: given a number of software products and certain constraints, how to load every node with software in a way that the size of the largest CVG is minimized? One important assumption here is that vulnerabilities are unique for different software packages. Thus diverse software is vulnerable to different exploits and will not be compromised by the same attack. This assumption is confirmed by [START_REF] Han | On the effectiveness of software diversity: A systematic study on real-world vulnerabilities[END_REF], in which it is found that more than 98.5% software have the substitutes and majority of them do not have the same vulnerabilities.

We are looking for a coloring assignment that satisfies above requirements and serves the goal of minimizing the largest CVG. Let C h and C s denote host and software constraints respectively. Next, we give a formal description of our software assignment problem.

Problem Given a weighted communication graph G = (V, E, W ) and a set of colors C, for each

v i ∈ V assigns a subset x(v i ) ⊆ C, such that, -v i gets w(v i ) ∈ W distinct colors, satisfying constraints C h and C s ; -for ∀c ∈ C, CVGs S i (c) ∩ S j (c) = ∅, for any i = j ;
-the size of the largest CVG is minimized.

The software assignment problem can be solved in either NP-time or P-time, depending on the given constraints. Our problem without considering constraints is a more general problem than ordinary vertex coloring, hence it is NP-hard in those cases where vertex coloring is NP-hard. And polynomial-time algorithms can be expected only in those cases where vertex coloring is polynomial-time solvable. We can expect that in certain situations, the special case of coloring is easier to solve than the general problem. Considering an extreme example when there are sufficient constraints that pre-define all the colors of vertices in G. In this situation, assignment solution can be obtained with O(1). For some cases, however, not only our problem is NP-hard, but the case with constraint(s) is hard as well. In an example where there is only one constraint that pre-assigns a vertex v 1 with color red, the graph G = (V, E, W ) can then be updated to G = (V, E, W ) by doing w (v 1 ) = w(v 1 ) -1. The problem then becomes multicoloring on graph G , which is still NP-hard. It is worthwhile to study some restricted form of coloring with local constraints (e.g., give a bound on the number of constrained vertices), in the hope of finding a polynomial time solvable case. Since our problem can be NP-hard, optimal solutions may only be found when graphs are relatively small. Heuristics are needed to study large graphs. In the next section, we present a greedy algorithm to address the problem of software assignment with arbitrary constraints.

Software Assignment Algorithm

In this section, we present our algorithm for software assignment, which will produce an assignment of colors to vertices in a graph, subject to a set of constraints defined in the previous section.

Formulating Constraints

To incorporate host constraints to the algorithm, we introduce a collection of tuples CST R h = {(v i , ε)} where v i is a vertex in the communication graph and ε is a (set of) color value(s) indicating that vertex v i is constrained by color(s) in ε. For example, C h = {(v 1 , {c 1 , c 2 }), (v 3 , {c 5 })}, means vertices v 1 and v 3 are fixed with colors c 1 and c 2 , and color c 5 , respectively. Similarly, we denote software constraint using CST R s = (s, ε), where s is the indicator of codependent colors and ε is a set of colors. When s equals 0, it states that the set of colors in set ε must not be assigned together to any vertex. In contrast, 1 means that colors in ε must be allocated simultaneously in order to perform certain functionality. For example, assume for an assignment characterized by C s = {(0, {c 1 , c 2 , c 4 }), (1, {c 1 , c 3 })} on which c 1 , c 2 , c 3 represent three distinct software with equivalent functionality, one may prefer not to coloring the single vertex with any combination of c 1 , c 2 and c 4 , (i.e., assigning them simultaneously) while colors c 1 and c 3 must be assigned together to this vertex.

Algorithm Description

The algorithm consists two phases: a labeling phase and a coloring phase. In the labeling phase, each vertex is assigned a distinct number as its label and ordered based on that label. Following the labeling phase, the second phase of the algorithm colors vertices in the ordered list sequentially. It works by first scanning the vertices in a graph and load each vertex as many colors as possible while making sure not to create defective edges. It then visits all the vertices that have not been completely colored in order. Upon visiting a particular vertex, the algorithm assigns a color that leads to minimum CVG.

Phase 1-Labeling. We initialize a set UNCOLOR to contain all the ordered, uncolored vertices and we assume that the available colors in the palette C are suitably ordered as

C = {c 1 , c 2 , • • • , c k },
where k = |C|. The main process then assigns every vertex a unique number from 1 to n as its label, where n is the total number of vertices in the network graph. Next, based on the numbers assigned, we order the vertices in UNCOLOR so that vertices with smaller labels are listed first. Several ordering heuristics are available to help accomplish the task of labeling: random ordering, increasing degree ordering, and decreasing degree ordering. Here we choose random ordering as the basis of our labelling. The randomness is intentionally designed so that one can run our algorithm once again to get a new color assignment solution by reordering the vertices. Certainly, an important property would be that the qualities of the assignments need to be stable. It means the largest CVGs resulted from different assignments are about the same size. The effect of the ordering will be evaluated in Section 5.

Phase 2-Coloring. The coloring task of phase 2 is done by two procedures: ColorVertexI and ColorVertexII. In the coloring phase, ColorVertexI first applies host constraint and assigns pre-determined colors to certain vertices while satisfying the software constraint. After that, it then successively colors the ordered vertices through the iterative processes. When a current color is determined, the algorithm scans the vertices in UNCOLOR sequentially checking to see if any of them can be colored according to the rules-1) no two adjacent vertices share the same color; 2) software constraints are satisfied by assigning the color. Meanwhile, ColorVertex I also checks the constraint sets to ensure that all the pre-defined constraints are satisfied by assigning the colors. Noted that followed by each coloring action, both the weight and UNCOLOR set need to be updated. When a vertex v i is assigned the current color, the weight w i corresponding to it will be decreased by 1 by doing w i = w i -1. Those vertices with weight equals to 0 will be removed from UNCOLOR (i.e., UNCOLOR = UNCOLOR -v i ). If the vertex violates any constraints or its weight is larger than 0, then this vertex will remain in UNCOLOR for next iteration. The process of ColorVertexI stops when either the UNCOLOR set is empty or no feasible colors can be assigned to any vertices in UNCOLOR set.

Although ColorVertexI limits the number of defective edges to the minimum extent, there is a high probability that not all vertices get colored due the rigorous coloring constraints of the algorithm. To further color those remaining vertices, we propose ColorVertexII. As a supplement to ColorVertexI, ColorVer-texII releases some of the hard requirements by allowing certain adjacent vertices to share the same color. However, with the overall goal of increasing the survivability of a networked system, such release should still follow certain principles. To be specific, instead of targeting at controlling the number of defective edges (keep it as 0), ColorVertexII shifts its focus to minimizing the size of the maximal CVG. For better understanding, we use an example to illustrate our point. Given two graphs in Fig. 3. The left graph has 3 defective edges ({v 1 , v 7 }, {v 3 , v 7 }, {v 6 , v 7 }) but none of them share a common vertex; the graph on the right contains 3 defective edges ({v 1 , v 4 }, {v 2 , v 4 }, {v 4 , v 8 }) but all share a common vertex v 4 . Accordingly, the maximal infectable number in the left graph is 2 (assuming the attack starts from one node), whereas for the graph on the right, this number is 4. Hence, if an attack takes place on both graphs, the potential damage in the left graph is smaller than that in the other graph even though the left graph has a larger number of defective edges.

After ColorVertexI, if UNCOLOR set is empty, it returns a perfect coloring solution where no adjacent nodes share same colors. Otherwise, ColorVertexII is called after ColorVertexI finishes. It tries every color one by one in the UN-COLOR set and choose one with the least penalties. Since penalty occurs when defective edges appear, least penalties means that with the color assigned to the particular vertex, it forms up a smaller CVG compared to all other colors. This process repeats until UNCOLOR set is empty. 1: initialize array X 2: for l ← 1 to n -1 do 3:

Algorithm 1 Color Assignment Algorithm

pick unlabelled v ∈ V

Algorithm Complexity Analysis

Initially, n nodes in graph G are available for coloring. In ColorVertexI, as all available colors (k) have to be tentatively assigned to every node, so there are n * k checks in this step. Suppose there are n remaining uncolored nodes in the worst case, each node with w i colors needs to be assigned, in ColorVertexII we need n * w i * k rounds to pick the optimal color for each of them. To satisfy the algorithm constraints, after each color allocation, ColorVertexII also needs to check the size of the CVGs containing the current node in order to find the optimal color assignment with the minimal value. This makes the time complexity of ColorVertexII O(n * k + n * w avg * n i * k), where w avg is the average number of weights for all of the nodes in the network, and O(n 2 * k) in the worst case (the expanded vertex set size for each color in ColorVertexII is as large as the entire graph when n i becomes n).

It is easy to show that if colors are fully available at each vertex during the coloring phase of our algorithm, i.e., |L(v i )| = k, and the maximum degree in the Fig. 3. Two random graphs with different software assignments graph ∆ = max 0 =i =N d(v i ), an optimal software assignment can eliminate the existence of defective edges if the number of available colors for the to-be-colored node k ≥ ∆ + 1. This matches the well-known conclusion in graph coloring that, the chromatic number of a graph is at most ∆ + 1 [START_REF] Welsh | An upper bound for the chromatic number of a graph and its application to timetabling problems[END_REF]. It is also practically useful to derive a theoretical lower bound of m = |C| on an arbitrary graph for a software assignment solution. However, it is difficult to analyze its lower bound when the system requirements and constraints vary across the network without restricting the constraints. For the case where there is no constraints, the lower bound of number had been discussed and proved [START_REF] Bollobás | The chromatic number of random graphs[END_REF]. Another extreme case is when all vertices of graph have been completely colored by predefined constrains. In this case, the chromatic number is exactly the number of colors of the graph.

Evaluations

In this section, we present simulation results for evaluating the performance of our method with respect to the above-mentioned requirements.

Simulation Setup

Recall that our model is built on top of undirected graph G as the abstraction of networked systems (Section 2.1). To fully investigate the performance of our algorithm in arbitrary systems, we use three representative topologies to characterize the behaviors of different systems. Specifically, we consider three types of graphs with different degree distributions: random graph, regular graph and power-law graph. A regular graph does not have high connectivity in many cases and thus long and circuitous routes are required to reach other nodes. Typical examples of regular graphs includes lattice and ring lattice graph, which can be used to characterize the behavior of each vertex that depends upon the behavior of its nearest neighbors. In a random graph, each pair of vertices are connected with the same probability and the degrees of each vertex are distributed according to a binomial distribution. In a power-law graph, the degree distribution satisfies a power law. It contains highly connected nodes (hubs) and is a good model for the highly connected systems. Scale-free networks follow power-law and many well-known networks such as WWW and social networks are believed to be scale-free [22]. We believe these three types of graphs provide a reasonable coverage range of realistic networked systems.

In this simulation, we generate graphs using igraph package in R with approximately the same average degree of 8. Given approximately the same degree settings across tested graphs, we observe if network connectivity affects the defense capability of our method. The default size for graphs in our experiment is 1000. Since our proposed mechanism only targets on networked systems with central authority (so that assigning software could be possible), the size of network chosen for experiment is reasonable and adequate to illustrate the results of our study. All simulation results here are presented as the average of 50 trials.

To evaluate our approach under various settings, we run the simulations with different combinations of the number of colors and weights, which is denoted as #color and #weight, respectively. The total #color in the "color pool", represents the unique number of software choices available for hosts to choose from, and #weight represents the average number of distinct software finally installed on each host. We further define r = #weight/#color. In our simulation we set #color to 30 by default. We believe 30 is a reasonable number to illustrate the properties of our algorithm (Section 6 will discuss how to reduce the number of colors for a real system). In order to see how the number of average weight impacts the performance metrics, #weight is set to be an integer value ranging from 1 to 20. Intuitively, the larger r, the less heterogeneity of the system. We avoid choosing values larger than 20 because when it exceeds 20, the whole system becomes almost homogeneous.

Simulation Metrics

We adopt two metrics while evaluating the performance of our approach, including 1) the maximal number of nodes that can be possibly compromised; 2) the average size of isolated CVGs. For the first metric, we define S as the number of nodes contained in the largest CVG, denoting the number of machines compromised under the worst-case attacks. Nodes within the maximal CVGs are always attackers' first choice to penetrate into the network. In addition to that, we also consider the average size of CVGs, which indicates the overall robustness of the system. Although solely depending on the average size of CVGs may not directly indicate the survivability of the system, when taking it into considerations together with S, it can somehow be used to present separate infections caused by an attack. We use a symbol s to denote the average size of CVGs in the system.

Simulation Results

Impact of r. First, we use the power-law graph as an example to show how r = #weight/#color impacts the heterogeneity of a system. Fig. 4 shows the variation of the largest CVG size S in responding to the changes of #weight and #color in a power-law graph.

We observe that given the same #color, when #weight increases, the CVG size S becomes greater. In addition to the general distribution, we also notice that all three lines with different #color generate relatively flat trends at the beginning and are followed by a sharp increase when r reaches 0.4. Before this critical point, S remains relatively small (i.e., when r < 0.4, S is less than 50). However, after r exceeds 0.4, S begins to increase rapidly.

The simulation results indicate that the degree of heterogeneity our algorithm can create actually depends on the value of r. In general greater r tends to generate larger CVG, which in turn indicates a more homogeneous system. For instance, when #weight equals to #color (r = 1), there is only one component in the graph (the worst case). The results also suggest very limited decrease of the CVG size when r is less than 0.4. Hence, for systems already with a r value less than 0.4, there is little need to reduce the #weight (e.g., by decreasing the number of software packages to be installed in each host) to prevent automated attacks. Impact of Network Topology. Next we conduct simulation to see how different network topologies might affect the CVG size (S) and the average size of isolated CVGs (s). As can be seen from Fig. 5, although the same "flat to sloping" trends are also observed in all three different topologies, we find that the CVG size of a power-law graph actually starts to increase at a relatively low r value (0.4) as compared to the cases of a random graph (when r = 0.5) and a regular graph (when r = 0.6). The difference in "turning point" is due to the distinct connectivity of each kind of topology. Given the existence of high connectivity nodes in a power-law network, large CVGs tend to be more easily formed than in the other two types of graphs. In contrast, as characterized by low connectivity and relatively high cliquishness [START_REF] Premo | Local extinctions, connectedness, and cultural evolution in structured populations[END_REF], a regular graph only generates large CVGs with larger r.

Besides the measurement on the CVG size, we also monitor the average size of all CVGs s. Unlike our prior observations, we find that the distribution s with r increases gently this time. Although there also appear to be some turning points in all three distributions, even if r exceeds the threshold, s remains relatively small values (when r reaches 0.6, s of three graphs is still smaller than 50) as compared to the CVG sizes. The explanation of this phenomenon is that, when a CVG is formed (after r exceeds the threshold), the sizes of CVGs become polarized. That is, except the maximal ones which are very large, the other CVGs are relatively small (sizes between 1 to 50).

The above results are useful as they suggest that organizations with limited budget or software availability can still enhance their system heterogeneity by changing the underlying topology if possible. Comparison with Other Algorithms. We next compare our algorithm with two related algorithms, randomized coloring and color flipping, as proposed in a previous study [START_REF] O'donnell | On achieving software diversity for improved network security using distributed coloring algorithms[END_REF]. In randomized coloring, each node picks a tentative color uniformly at random from the color pool, whereas color flipping extends the random coloring by allowing each node performs a local search amongst its immediate neighbors to switch colors to decrease the number of locally defective edges. Besides, we also compare our algorithm with the optimal solution based on brute-force search. We compare these algorithms in terms of the CVG size (S) as a function of r. Results are plotted in Fig. 6. As we can see from the figure, our algorithm outperforms both randomized coloring and color flipping methods by creating smaller CVGs given the same r. Scalability and Computational Overhead. Finally, we repeat the experiment on graphs of larger size and measure the computational overhead introduced by our algorithm. Even though Fig. 7 shows the average time required by this assignment algorithm grows exponentially with size of the network, it still suggests our algorithm can be applied to large systems with thousands of nodes with acceptable time overhead. As showed in Fig. 7, in a commodity PC, it takes about 10 minutes to assign colors to 10 thousand nodes. The simulation result confirms the practicability of our algorithm. Source of Diverse Software. In our problem setting, software diversity could be caused by a number of factors. First, installing different types of software on adjacent machines is itself a type of software diversity. One might doubt that if enterprises are willing to invest amounts of resources (e.g., purchasing licenses, training employees) to realize the mechanism. However, there is always a trade-off between security and costs. We believe the insights from the simulation results could help to ease the issue of finding the balance. Second, software of the same type might be implemented independently. For example, a number of web browsers are freely available, e.g., Firefox, IE, Chrome, so we may assume their vulnerabilities are different [START_REF] Han | On the effectiveness of software diversity: A systematic study on real-world vulnerabilities[END_REF], and consider them as different colors. Third, with new compiler technique [START_REF] Jackson | Compiler-generated software diversity[END_REF], each download of a piece of software could be a variant version of the client software which may not share the same vulnerability. Vulnerabilities in Software Another thing needs to be clarified in the context is that we do not actually need full knowledge of vulnerabilities (e.g., types and the exact number) in the software to be assigned. Given a software assignment solution, no matter how many vulnerabilities residing in a software product, even if it has an unknown vulnerability, CVGs of the graph remain the same. For the same reason, we can further shrink the size of "color pool" by considering multiple software packages as one single software product that can be represented by using a single color. For instance, all the standard software packages (including network services) come with Windows 7 in a batch, so the entire package of the standard Windows 7 distribution will only considered as one color. The edge between two adjacent hosts is defective as long as they both install Windows 7. For each (third-party) application installed later on, it may be considered as one color if it provides some network services. Severity Level of Vulnerability. In reality, vulnerabilities often have different levels of severity. The risks of some vulnerabilities are minor while some may be quite significant. For two CVGs of the same size, a more severe vulnerability (e.g., gain complete control of a system) could result in a far more serious damage compared to a mild vulnerability (e.g., allow an attacker to collect some types of user information). As such, we may use different values to represent different levels of damage that could be resulted from an attack, and our objective of optimization will then become to minimize the overall damage by the attack. In our future work we will devise a new algorithm by taking into account this dimension.

Conclusions

In this work, we proposed a method for effectively containing automated attacks via software diversity. By building up a heterogeneous networked system, our defense mechanism increases the complexity of the networked system by utilizing off-the-shelf diverse software. Given the practical problems of software assignment, we presented a software assignment algorithm based on graph multicoloring with real world constraints and system prerequisites. We analyzed the effectiveness of our methodology through extensive simulation study.

Fig. 1 .

 1 Fig. 1. Network topology utilizing a diverse software distribution. Solid lines connect nodes with the same color and indicate all possible worm-spreading paths; dashed lines connect nodes of different colors and indicate all non-spreading connections.

Fig. 2 .

 2 Fig. 2. Example of an enterprise network and its corresponding communication graph.

Input: ( 1 )

 1 Graph G = (V, E, W ); (2) Available colors are ordered and represented by integers 1, 2, • • • , k; (3) Ordering ω of vertices in V ; (4) Constraint sets C h and Cs; Output: A color assignment of k colors, 1 through k, to vertices of G represented by an array.

Fig. 4 .

 4 Fig. 4. S as a function of #weight and #color.

Fig. 5 .

 5 Fig. 5. Performance on three representative graphs.

Fig. 6 .

 6 Fig. 6. Comparison with other algorithms

Fig. 7 .

 7 Fig. 7. Time overhead (in seconds) 6 Discussion and Future Work

  for for each vertex j related by constraint c h (j) ∈ C h do

		at random
	4:	label(v) ← l
	5: end for
	6: UNCOLOR ← V
	7: UNCOLOR ← ApplyConstraint(G, C h ) 8: for i from the smallest to largest integer (color) do
	9:	for each vertex e in UNCOLOR do
	10:	ColorVertexI(G, Cs, i, e)
	11:	end for
	12: end for
	13: if (UNCOLOR == ∅) then exit
	14:	for each vertex e in UNCOLOR do
	15:	ColorVertexII(G, Cs, e)
	16:	end for
	17: end if
	18:
	19: procedure ApplyConstraint(G, C h ) 20:
	21: 22:	color(X[j]) ← c h (j).ε update wj and UNCOLOR
	23:	end for
	24:	return(UNCOLOR)
	25: end procedure
	26:
	27: procedure ColorVertexI(G, Cs, i, e)
	28:
		If so, color(X[e]) ← i
	31:	update we and UNCOLOR
	32:	end for
	33: end procedure
	34:
	35: procedure ColorVertexII(G, C h , e) 36: size = ∞
	37:	Select color icolor that results in the smallest CVG
	38:	color(X[e]) ← icolor
	39:	update we and UNCOLOR
	40: end procedure

for each vertex r that directly connects to e do

29:

check L(r) and Cs to see if i is a valid color for e 30:

Acknowledgement: The work of Sencun Zhu was supported in part by NSF grant CCF-1320605 and a Google gift. We also thank the reviewers for helpful comments.