Jonathan L Dautrich
email: dautricj@cs.ucr.edu

Chinya V Ravishankar

Security Limitations of Using Secret Sharing for Data Outsourcing

Three recently proposed schemes use secret sharing to support privacy-preserving data outsourcing. Each secret in the database is split into n shares, which are distributed to independent data servers. A trusted client can use any k shares to reconstruct the secret. These schemes claim to offer security even when k or more servers collude, as long as certain information such as the finite field prime is known only to the client. We present a concrete attack that refutes this claim by demonstrating that security is lost in all three schemes when k or more servers collude. Our attack runs on commodity hardware and recovers a 8192-bit prime and all secret values in less than an hour for k = 8.

Introduction

As cloud computing grows in popularity, huge amounts of data are being outsourced to cloud-based database service providers for storage and query management. However, some customers are unwilling or unable to entrust their raw sensitive data to cloud providers. As a result, privacy-preserving data outsourcing solutions have been developed around an honest-but-curious database server model. In this model, the server is trusted to correctly process queries and manage data, but may try to use the data it manages for its own nefarious purposes.

Private outsourcing schemes keep raw data hidden while allowing the server to correctly process queries. Queries can be issued only by a trusted client, who has insufficient resources to manage the database locally. Most such schemes use specialized encryption or complex mechanisms, ranging from order-preserving encryption [START_REF] Agrawal | Order preserving encryption for numeric data[END_REF], which has limited security and high efficiency, to oblivious RAM [START_REF] Stefanov | Towards practical oblivious RAM[END_REF], which has provable access pattern indistinguishability but poor performance.

Three recent works [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF][START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF][START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF] propose outsourcing schemes based on Shamir's secret sharing algorithm [START_REF] Shamir | How to share a secret[END_REF] instead of encryption. We refer to these works by their authors' initials, HJ [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF], AAEMW [START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF], and TSWZ [START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF], and in aggregate as the HAT schemes. The AAEMW scheme was also published in [START_REF] Agrawal | Database Management as a Service: Challenges and Opportunities[END_REF]. In secret sharing, each sensitive data element, called a secret, is split into n shares, which are distributed to n data servers. To recover the secret, the client must combine shares from at least k servers. Secret sharing has perfect information-theoretic security when at most k -1 of the n servers collude (exchange shares) [START_REF] Shamir | How to share a secret[END_REF].

Since secret sharing requires only k multiplications to reconstruct a secret, proponents argue that HAT schemes are faster than encryption based schemes.

Other benefits of the HAT schemes include built-in redundancy, as only k of the n servers are needed, and additive homomorphism, which allows SUM queries to be securely processed by the server and returned to the client as a single value. Each of the HAT schemes makes two security claims: Claim 1. The scheme achieves perfect information-theoretic security when at most k -1 servers collude.

Claim 2. When k or more servers collude, the scheme still achieves adequate security as long as certain information used by the secret sharing algorithm, namely a prime p and a vector X, are kept private, known only to the client.

It is doubtful that the HAT schemes truly fulfill Claim 1, as they sort shares by secret value, which certainly reveals some information about the data [START_REF] Kantarcioglu | Security issues in querying encrypted data[END_REF]. Further, the AAEMW scheme [START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF] uses correlated coefficients in the secret sharing algorithm instead of random ones, which also contradicts this claim. Nevertheless, for the purposes of this work, we assume that Claim 1 holds.

We are primarily concerned with evaluating Claim 2, which asserts that even k or more colluding servers cannot easily recover secrets. Claim 2 is stated in Sect. 4.5 of [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF], Sect. 3 of [START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF], Sects. 2.2 and 6.1 of [START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF], and Sect. 3 of [START_REF] Agrawal | Database Management as a Service: Challenges and Opportunities[END_REF].

Our Contribution

Our contribution is to demonstrate that all three HAT schemes [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF][START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF][START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF] fail to fulfill Claim 2. We give a practical attack that can reconstruct all secrets in the database when k servers collude, even when p and X are kept private. Our attack assumes that the servers know, or can discover, at least k + 2 secrets. To limit data storage costs, k is kept small (k ≈ 10), so discovering k + 2 secrets is feasible (see Sect. 4.2). All three HAT schemes argue that they fulfill Claim 2, so our result provides a much-needed clarification of their security limitations.

The TSWZ scheme [START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF] argues that if p is known, secrets could be recovered. However, it provides no attack description, and argues that large primes are prohibitively expensive to recover. Our attack recovers 8192-bit primes in less time than [START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF] needed to recover 32-bit primes. In fact, we can generally recover large primes in less time than the client takes to generate them (Sect. 5.1).

In Sect. 2 we review Shamir's secret sharing algorithm and how it is used for private outsourcing. In Sect. 3 we give assumptions and details of our attack, and we show how to align shares and discover secrets in Sect. 4. We give experimental runtime results in Sect. 5, and discuss possible attack mitigations in Sect. 6. We discuss related work in Sect. 7 and conclude with Sect. 8.

Data Outsourcing Using Secret Sharing

We now review Shamir's secret sharing scheme and show how it is used for private data outsourcing in the HAT schemes [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF][START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF][START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF]. We use an employee table with m records as our driving example, where queries are issued over the salary attribute. Each salary s 1 , . . . , s m is a secret that is shared among the n data servers (see Fig. 1).

Shamir's Secret Sharing

Shamir's secret sharing scheme [START_REF] Shamir | How to share a secret[END_REF] is designed to share a single secret value s j among n servers such that shares must be obtained from any k servers in order to reconstruct s j . The scheme's security rests on the fact that at least k points are needed to uniquely reconstruct a polynomial of degree k -1. Theoretically, the points and coefficients used in Shamir's scheme can be taken from any field F. However, to use the scheme on finite-precision machines, we require F to be the finite field F p , where p is a prime.

To share s j , we choose a prime p > s j , and k -1 coefficients a 1,j , . . . , a k-1,j selected randomly from F p . We then construct the following polynomial:

q j (x) = s j + k-1 h=1 a h,j x h mod p (1)
We then generate a vector X = (x 1 , . . . , x n ) of distinct elements in F p , and for each data server DS i , we compute the share y i,j = q j (x i ). Together, x i and y i,j form a point (x i , y i,j ) through which polynomial q j (x) passes.

Given any k such points (x 1 , y 1,j ), . . . , (x k , y k,j ), we can reconstruct the polynomial q j (x) using Lagrange interpolation:

q j (x) = k i=1 y i,j i (x) mod p (2)
where i (x) is the Lagrange basis polynomial:

i (x) = 1≤j≤k,j =i (x -x j )(x i -x j ) -1 mod p (3)
and (x i -x j ) -1 is the multiplicative inverse of (x i -x j ) modulo p.

The secret s j is the polynomial q j evaluated at x = 0, so we get:

s j = k i=1 y i,j i (0) mod p (4)
Given only k < k shares, and thus only k points, we cannot learn anything about s, since for any value of s, we could construct a polynomial of degree k -1 that passes through all k points. Thus Shamir's scheme offers perfect, information-theoretic security against recovering s j from fewer than k shares [START_REF] Shamir | How to share a secret[END_REF].

Data Outsourcing via Secret Sharing

We now describe the mechanism used by all three HAT schemes to support private outsourcing via secret sharing. We first choose a single prime p and a vector X, which are the same for all secrets and will be stored locally by the client. For each secret s j , we generate coefficients a 1,j , . . . , a k-1,j , and produce a polynomial q j (x) as in [START_REF] Agrawal | Order preserving encryption for numeric data[END_REF]. We then use q j to split s j into n shares y 1,j , . . . , y n,j , where y i,j = q j (x i ), and distribute each share y i,j to server DS i , as in Fig. 1.

An important distinction is that the AAEMW scheme performs secret sharing over the real number field R, so there is no p to choose. However, since the scheme must run on finite precision hardware, any implementation will suffer from roundoff error. Our attack works over R, and is efficient because the field is already known. However, we expect that in practice, the AAEMW scheme will switch to a finite field F p , so we do not treat it as a special case.

When the client issues a point query for the salary s j of a particular employee, he receives a share from each of the n servers. Using any k of these shares, he can recover s j using the interpolation equation ( 4). Other query types, including range and aggregation queries, are supported by the HAT schemes. We give some relevant details in Sect. 2.4, but the rest can be found in [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF][START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF][START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF].

X and p are re-used across secrets for two reasons. First, storing distinct X or p on the client for each secret would require at least as much space as storing the secret itself. Second, when the same X and p are used, the secret sharing scheme has additive homomorphism. That is, if each server DS i adds shares y i,1 + y i,2 , and we interpolate using those sums, the recovered value is the sum s 1 + s 2 . With additive homomorphism, when the client issues a SUM query, the server can sum the relevant shares, and return a single value to the client, instead of returning shares separately and having the client perform the addition. Using a different X or p for each secret breaks additive homomorphism.

Security

If X and p are public, and k or more servers collude, then the HAT schemes are clearly insecure, as the servers could easily perform the interpolation themselves. On the other hand, if at most k -1 servers collude, and coefficients are chosen independently at random from F p , then the servers learn nothing about a secret by examining its shares, and Claim 1 is fulfilled.

The HAT schemes state that by keeping X [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF][START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF] and p [5] private, they achieve security even when k or more servers collude (Claim 2). Our attack shows that any k colluding servers can recover all secrets in the database, even when X and p are unknown (Sect. 3), contradicting Claim 2.

Supporting Range and Aggregation Queries

We can use the mechanisms that support range and SUM queries in the HAT schemes to reveal the order of the shares on each server according to their corresponding secret values. We then use these orders to align corresponding shares across colluding servers, and to discover key secret values (see Sect. 4).

The AAEMW scheme [START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF] crafts coefficients such that the shares preserve the order of their secrets. The HJ and TSWZ schemes [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF][START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF] both use a single B + tree to order each server's shares and facilitate range queries. TSWZ assumes the tree is accessible to all servers, while HJ assumes it is on a separate, non-colluding index server. HJ obscures share order from the servers, but we can reconstruct it by observing range queries over time (see Sect. 4.3).

Attack Description

We now show that the HAT schemes are insecure when k or more servers collude, even if X and p are kept private. Our attack efficiently recovers all secret values (salaries in Fig. 1) stored in the database, and relies on the following assumptions:

1. At least k servers collude, exchanging shares or other information. 2. The number of servers k and the number of bits b in prime p are modest: k ≈ 13, b ≈ 2 13 . None of the HAT schemes give recommended values for k or b, with the exception of a brief comment in [START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF] alluding to 16-bit primes originally suggested by Shamir. In practice, primes with more than 2 13 bits take longer for the client to generate than for our attack to recover, and the cost of replicating data to every server keeps k small. 3. X and p are unknown, and are the same for each secret (see Sect. 2.2). 4. Each set of k corresponding shares can be aligned. That is, the colluding servers know which shares correspond to the same secret, without knowing the secret itself. We can align shares if we know share orders (see Sect. 4.1). 5. At least k + 2 secrets, and which shares they correspond to, are known or can be discovered. Since k is modest, knowing k + 2 secrets is reasonable, especially when the number of secrets m is large (see Sect. 4.2).

In Sect. 6, we show that modifying the HAT schemes to violate these assumptions sacrifices performance, functionality, or generality, eroding the schemes' slight advantages over encryption based techniques.

Recovering Secrets when p is Known and X is Private

As a stepping stone to our full attack, we show how to recover secrets if p is already known. Without loss of generality, let s 1 , . . . , s k be known secrets, and let DS 1 , . . . , DS k be the colluding servers. For each secret s j , we have shares y 1,j , . . . y k,j , generated by evaluating q j (x) at x 1 , . . . , x k , respectively. We therefore have a system of k 2 equations of the form y i,j = s j + k-1 h=1 a h,j x h i mod p, as in [START_REF] Agrawal | Order preserving encryption for numeric data[END_REF]. The system has k(k -1) unknown coefficients a h,j , and k unknown x i , giving k 2 equations in k 2 unknowns. Thus, it would seem we can solve for the relevant values of X, which would allow us to recover the remaining secrets. Unfortunately, the system is non-linear, so naively solving it directly requires expensive techniques such as Groebner basis computation [START_REF] Buchberger | Gröbner bases and applications[END_REF].

Instead, we can recover the remaining secrets without solving for X. Consider the following system of equations obtained by applying the interpolation equation ( 4) to each of the k secrets:

y 1,1 1 (0) + y 2,1 2 (0) + • • • + y k,1 k (0) -s 1 ≡ 0 (mod p) y 1,2 1 (0) + y 2,2 2 (0) + • • • + y k,2 k (0) -s 2 ≡ 0 (mod p) . . . ( 5
)
y 1,k 1 (0) + y 2,k 2 (0) + • • • + y k,k k (0) -s k ≡ 0 (mod p)
If we treat each basis polynomial value i (0) as an unknown, we get k unknowns 1 (0), . . . , k (0), which we call bases, in k linear equations. Since we know p, we can easily solve (5) using Gaussian elimination and back-substitution. We can then use the bases to recover the remaining secrets in the database via [START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF].

We can construct (5) since we know that all shares from a given server DS i were obtained from the same x i , and thus should be multiplied by the same base i (0). The client could obscure the correspondence between shares by mixing shares among servers, but would be forced to store i with each share in order to properly reconstruct the secret. To completely hide the correspondence, i itself would need to be padded and encrypted, which is precisely what secret sharing tries to avoid. Further, mixing the shares would break additive homomorphism.

Recovering p when X and p are Private

Let b be the number of bits used to represent p. We can easily have b > 2 6 , so enumerating possible values for p is not practical. However, we can recover p by exploiting known shares and the k + 2 known secrets. Our attack identifies two composites δ 1 and δ 2 both divisible by p (p|δ 1 , p|δ 2 ), such that the remaining factors of δ 1 , δ 2 are largely independent. We then take δ to be the greatest common divisor of δ 1 and δ 2 , and factor out small primes from δ , leaving us with δ = p with high probability. Once p is known, we can use the attack from Sect. 3.1 to recover the bases and the remaining, unknown secrets.

Computing δ 1 , δ 2 . Without loss of generality, we let s 1 , . . . , s k+2 be the known secrets. To compute δ γ , γ ∈ {1, 2}, we consider the system of interpolation equations for secrets s γ , . . . , s γ+k as in [START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF], represented by the following (k + 1) × (k + 1) matrix:

       y 1,γ y 2,γ • • • y k,γ -s γ y 1,γ+1 y 2,γ+1 • • • y k,γ+1 -s γ+1 . . . . . . . . . y 1,γ+k-1 y 2,γ+k-1 • • • y k,γ+k-1 -s γ+k-1 y 1,γ+k y 2,γ+k • • • y k,γ+k -s γ+k        (6)
Since p is unknown, we cannot compute inverses modulo p and thus cannot divide as in standard Gaussian elimination. However, we can still convert (6) to upper triangular (row echelon) form using only multiplications and subtractions.

We start by eliminating coefficients for 1 (0) from all but the first row (j = γ). To eliminate 1 (0) from row j > γ, we multiply the contents of row γ through by y 1,j , and of row j by y 1,γ , producing a common coefficient for 1 (0) in both rows. We then subtract the multiplied row γ from the multiplied row j, canceling the coefficient for 1 (0). Row 1 is left unchanged, but row j now has coefficient 0 for 1 (0), and coefficient (y i,j )(y 1,γ ) -(y i,γ )(y 1,j ) for i (0), i ≥ 2:

     y 1,γ y 2,γ • • • -s γ 0 (y 2,γ+1 )(y 1,γ ) -(y 2,γ )(y 1,γ+1 ) • • • (-s γ+1 )(y 1,γ ) -(-s γ )(y 1,γ+1 ) . . . . . . . . . 0 (y 2,γ+k )(y 1,γ ) -(y 2,γ )(y 1,γ+k ) • • • (-s γ+k )(y 1,γ ) -(-s γ )(y 1,γ+k )     
We then repeat the process, eliminating successive coefficients from lower rows, until the matrix is in upper triangular form:

       y 1,γ y 2,γ • • • y k,γ -s γ 0 c 2,γ+1 • • • c k,γ+1 c k+1,γ+1 . . . . . . . . . 0 0 • • • c k,γ+k c k+1,γ+k 0 0 • • • 0 δ γ        (7)
We use c i,j values to denote constants. In the last row of ( 7), the coefficient for every i (0) is 0, so the row represents the equation δ γ ≡ 0 (mod p). Thus, p|δ γ .

Size of δ 1 , δ 2 . As coefficients for successive i (0) are eliminated, each non-zero cell below the ith row is set to the difference of products of two prior cell values, doubling the number of bits required by the cell. Thus, the number of bits per cell in ( 7) is given by: 

      b b • • • b b 0 2 1 b • • • 2 1 b 2 1 b . . . . . . . . . 0 0 • • • 2 k-1 b 2 k-1 b 0 0 • • • 0 2 k b       
As a result, each of δ 1 , δ 2 has at most 2 k b bits. This is closely related to the result that in the worst case, simple integer Gaussian elimination leads to entries that are exponential in the matrix size [START_REF] Fang | On the worst-case complexity of integer gaussian elimination[END_REF].

Recovering p from δ 1 , δ 2 . Since δ 1 , δ 2 have 2 k b bits, and p has only b bits, it is likely that δ 1 , δ 2 both have some prime factors larger than p, so factoring them directly is not feasible. Instead, we take δ = gcd (δ 1 , δ 2 ), where gcd is the greatest common divisor function, which can be computed using the traditional Euclidean algorithm, or more quickly using Stein's algorithm [START_REF] Stein | Computational problems associated with racah algebra[END_REF].

Since δ 1 and δ 2 were obtained using different elimination orders and sets of secrets, they rarely share large prime factors besides p, so all other prime factors of δ should be small. Thus, we can factor δ by explicitly dividing out all prime factors with at most β bits, leaving behind only p, with high probability. We know that p is larger than all shares, so to avoid dividing out p itself, we never divide out primes that are larger than the largest known share. We have found empirically that the probability that δ 1 , δ 2 , as computed above, share a factor with more than β bits can be approximated by 2 (k-2)/ 4 2 β+1 k for the values of β, k we are interested in (Sect. 5.2). Our attack fails if δ 1 , δ 2 share such a factor, but we can make the failure rate arbitrarily low by increasing β.

Attack Complexity

Since δ 1 and δ 2 are both (2 k b)-bit integers, the time required to find gcd [START_REF] Stein | Computational problems associated with racah algebra[END_REF]. As k grows, storing δ 1 , δ 2 and computing their gcd quickly become the dominant space and time concerns, respectively. Thus, recovering p has space complexity O(2 k b) and time complexity O(2 2k b 2 ).

(δ 1 , δ 2 ) is in O(2 2k b 2 )
Recovering the bases, once p is known, has space complexity O(k 2 b) for storing the matrix, and time complexity dominated either by computing O(k 3 ) bbit integer multiplications during elimination, or O(k) modular inverses during back-substitution. Clearly, these costs are dominated by the costs of recovering p. Once p and the bases have been recovered, the time spent recovering a secret is the same for the colluding servers as it is for the trusted client.

Example Attack for k = 2

We now demonstrate our attack on a simple dataset with m = 6 records shared over n = k = 2 servers. We choose the 6-bit prime p = 59 and select x 1 = 17, x 2 = 39. We then generate secrets, coefficients, and shares as follows:

s 1 = 18 a 1,1 = 18 q(x 1 , s 1 ) = 29 q(x 2 , s 1 ) = 12 s 2 = 36 a 1,2 = 5 q(x 1 , s 2 ) = 3 q(x 2 , s 2 ) = 54 s 3 = 22 a 1,3 = 17 q(x 1 , s 3 ) = 16 q(x 2 , s 3 ) = 36
s 4 = 10 a 1,4 = 28 q(x 1 , s 4 ) = 14 q(x 2 , s 4 ) = 40 s 5 = 39 a 1,5 = 31 q(x 1 , s 5 ) = 35 q(x 2 , s 5 ) = 9

s 6 = 57 a 1,6 = 51 q(x 1 , s 6 ) = 39 q(x 2 , s 6 ) = 40
We assume s 1 , s 2 , s 3 , s 4 are known. We first generate the matrix in (6) using s 1 , s 2 , s 3 (γ = 1), and do the following elimination to get δ 1 = 307980: We then compute δ = gcd (δ 1 , δ 2 ) = 2124, and factor δ by dividing out the small prime factors 2 • 2 • 3 • 3, to get p = 59, as expected. Now we can recover the bases using the following system of equations as in (5): 29 1 (0) + 12 2 (0) -18 ≡ 0 (mod 59) 3 1 (0) + 54 2 (0) -36 ≡ 0 (mod 59)

We eliminate 1 (0) from the second equation, giving 55 2 (0) ≡ 46 (mod 59). We then compute the inverse (55) -1 (mod 59) = 44, giving 2 (0) = 46•44 mod 59 = 18. We then back-substitute to get 1 (0) = 42. To verify, we compute s 5 and s 6 using (4), giving s 5 = 35 • 42 + 9 • 18 (mod 59) = 39, and s 6 = 39 • 42 + 40 • 18 (mod 59) = 57, as expected.

Aligning Shares and Discovering Secrets

In order to mount our attack, we must be able to align shares across colluding servers. That is, given the set of shares from each of k servers, we must be able to identify which subsets of k shares, one from each server, were obtained from the same polynomial q j (1), even if we do not know the secret value s j itself. Further, we must know, or be able to discover, at least k +2 secret values and the subset of k shares to which they correspond. We now show how we can satisfy these assumptions for the HAT schemes [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF][START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF][START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF] using knowledge of share order.

In the AAEMW [START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF] and TSWZ [START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF] schemes, the shares on each server are explicitly, totally ordered (Sect. 2.4). The share order sorts the shares in nondecreasing order of their corresponding secrets. If two shares are obtained from distinct polynomials, but the same secret, they have the same relative order on each server. In the HJ scheme [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF], shares are totally ordered, but the order is hidden from the data servers. In this case, we can infer a partial share order by observing queries over time.

Aligning Shares

When the total share order on each data server is known, we simply align the jth share from each server. If only a partial order is known, as in the HJ scheme, the alignment of some shares will be ambiguous. To recover secrets for such shares, we must either try multiple alignments, or wait for more queries to arrive, and use them to refine the partial order and eliminate the ambiguity (see Section 4.3).

Discovering k + 2 Secrets

We have shown that given k + 2 secrets and their corresponding shares, our attack can recover all remaining secrets. This weakness is a severe limitation of the HAT schemes, and contradicts Claim 2 (Sect. 1). In practice, k m, where m is the number of secrets, so assuming k + 2 known secrets is reasonable. Our attack is independent of the mechanism used to discover these secrets.

Simple methods for learning k + 2 secrets include a known plaintext attack, where we convince the trusted client to insert k + 2 known secrets, and a known ciphertext attack, where the client reveals at least k +2 secrets retrieved by some small range query. Since shares are ordered according to their secret values, we can easily identify which subsets of shares from the query go with each secret.

We can also infer secret values using share order. Consider an employee table with secret salaries, as in Fig. 1. If at least k + 2 employees earn a well-known minimum-wage salary, then the share order reveals that the first k+2 shares have this known salary. Alternatively, there may be k +2 employees who anonymously post their salaries. If we can estimate the distribution of salaries in the database, we can guess roughly where the known salaries fall in the order, and run the attack for nearby guesses until we get a solution with a recoverable prime and recovered secrets that fit the expected order.

Inferring Order in the HJ Scheme

If a scheme hides the share order from the data server, share alignment and secret discovery become harder. The HJ scheme [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF] stores the share order for each data server on a single index server that ostensibly does not collude with any data servers. The client sends each query to the index server, and the response tells the client which shares to request from each data server.

In the simplest case, we can align shares by observing point queries, which return only one share from each server. If the colluding servers all observe an isolated request for a single share at the same time, they can assume the shares satisfy a point query, and thus that they all correspond to the same secret. Given enough point queries, we can align enough shares to mount our attack. However, if point queries are rare, this technique will take too long to be useful.

More generally, we can order shares on each server by observing overlapping range queries. In the HJ scheme, a range query appears to the data server as set of unordered share requests. Since range queries request shares that have secrets inside a given range, we know that secrets of requested shares are contiguous. We use this information to order shares according to their secret values.

Consider an example where a client issues two range queries to the same data server. The first query returns shares {y 1 , y 2 }, and the second, shares {y 3 , y 2 }. Each query is a range query, so the server knows that no secret can fall between the secrets of y 1 and y 2 or of y 3 and y 2 . Since y 2 appears in both queries, the server knows that the secret of y 2 comes between the secrets of y 1 and y 3 , but is not sure whether the secret of y 1 or of y 3 is smaller. Thus, the true share order Query {y 3 , y 2 } Fig. 2. Range queries indicate that the secrets of shares y1, y2 are contiguous, as are those of y3, y2. Thus, the secret of y2 falls between the secrets of y1 and y3, though either y1 or y3 may have the smallest secret.

contains either subsequence y 1 y 2 y 3 or y 3 y 2 y 1 , and we say that the server knows the share order of {y 1 , y 2 , y 3 } up to symmetry (see Fig. 2).

We can extend this technique to additional range queries of varying sizes. Given enough queries, we can reconstruct the entire share order on each server up to symmetry. The full reconstruction algorithm uses PQ-trees [START_REF] Booth | Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms[END_REF], but is out of scope for this paper. We can link reconstructed share orders across servers, and thereby align shares, by observing that if a query issued to one data server requests the jth share, then the same query must also request the jth share from every other server. If we use the share order to discover secrets, we must make twice as many guesses, since we still only know the order up to symmetry.

Attack Implementation and Experiments

We implemented our attack in Java, and ran each of our attack trials using a single thread on a 2.4GHz Intel R Core TM 2 Quad CPU. All trials used less than 2GB RAM. We used two datasets. The first consists of m = 1739 maximum salaries of Riverside County (California, USA) government employees as of February, 2012 [START_REF]County of riverside class and salary listing[END_REF]. The second is a set of m = 10 5 salaries generated uniformly at random from the integer range [0, 10 7 ).

Time Measurements

Our first set of experiments measures the time required to run the full attack as described in Sect. 3. Each experiment varies the number of servers k or the number of bits b in the hidden prime p. The total number of servers n has no effect on the attack runtime, so we let n = k. All times are averaged over 10 independent trials, and averages are rounded up to a 1ms minimum. In each trial, we divide out primes with at most β = 16 bits (Sect. 3.2), and we successfully recover p, all k bases ( i (0) values), and all m secrets.

Each plot gives the times spent by the client finding a random b-bit prime p and creating k shares for each of the m secrets. We then plot the times spent by the colluding servers recovering p and the k bases. We also give the time spent recovering all m secrets, which is the same for the colluding servers as it is for the client. From Sect. 3.3, we know that the time needed to recover p is Figures 3 and4 plot times using the Riverside dataset with fixed b = 2 8 and k = 8, respectively. Figures 5 and6 give corresponding times for the random dataset. Times to create shares and recover secrets are proportional to m, and so are higher for the larger, random dataset. Times to generate p, recover p, and recover bases depend only on b and k, and so are dataset-independent.

Figures 3 and5 show that when k is held constant, increasing b costs the client more than it costs the colluding servers. Both prime recovery and modular multiplication take time proportional to b 2 , so prime recovery time is a constant factor of share generation time. Further, the time to choose a random b-bit prime [START_REF] Rabin | Probabilistic algorithm for testing primality[END_REF], so as b grows past 2 12 , the cost to generate p quickly outstrips the cost to recover it. Thus it is entirely impractical to thwart our attack by increasing b.

In the TSWZ scheme [START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF], the measured time to recover a prime with less than 2 5 bits was over 1500 seconds. In contrast, our method recovers primes with 2 13 bits in under 500 seconds on comparable hardware, for k = 8. As long as k b, as is likely in practice, our method is far faster.

Figures 4 and6 show that when b is fixed, most times are in O(k), with the exception of prime recovery time, which is in O(2 2k ). Thus, by increasing k, the attack can be made arbitrarily expensive at a relatively small cost to the client. However, as we discuss in Sect. 6, even k = 10 may be impractical.

Failure Rate Measurements

Since we only factor out small primes with at most β bits (Sect. 3.2), our attack fails if δ 1 , δ 2 share any prime factor, other than p, that has more than β bits. Thus, our attack's failure rate r f is the probability that δ 1 /p, δ 2 /p share a prime with more than β bits. Since δ 1 , δ 2 are not independent random numbers, it is difficult to compute r f analytically, so we measure it empirically. The results of our experiment are shown in Fig. 7.

We found that r f is largely independent of b, but depends heavily on k and β. To measure r f , we conducted several trials in which we generated a prime p of b = 32 bits, and ran our attack using k + 2 randomly generated secrets. For k = 2, we ran 10 6 trials, and were able to get meaningful failure rates up through β ≈ 16. Trials with larger k were much more expensive, so we only ran 10 3 trials for k = 6 and k = 10, and the results are accurate only through β ≈ 10.

From our results, we derived the approximate expression r f ≈ 2 (k-2)/4 2 β+1 k. We then plotted this estimated r f in Fig. 7, denoted by est. The approximation is adequate for the range of β we're considering. The dependence of r f on 2 -(β+1) is expected, as the probability that a factor of β + 1 bits found in one random d-bit = 2 -(β+1) . The nature of the dependence on k is unclear, but it may be related to the fact that k of the k + 1 equations used to compute δ 1 are also used to compute δ 2 .

Using our approximation for r f , we estimate the worst-case failure rate for our timing experiments, where β = 16 and k = 13, to be r f ≈ 2 (13-2)/4

2 16+1 13 = 2 -14.25 13 ≈ 6.67 × 10 -4 . If necessary, we can lower r f further by increasing β.

Attack Mitigations

We now discuss possible modifications a client can make to the HAT schemes that may improve security. In order to mitigate our attack, a modification must cause at least one of the attack assumptions listed in Sect. 3 to be violated.

Assumption: At Least k Servers Collude. The simplest way to thwart our attack is to ensure that no more than k -1 servers are able to collude. Only in such cases can secret sharing schemes hope to achieve perfect, information-theoretic security. However, if the number of colluding servers must be limited, secret sharing schemes cannot be applied to the honest-but-curious server threat model commonly used for data outsourcing [START_REF] Agrawal | Order preserving encryption for numeric data[END_REF][START_REF] Stefanov | Towards practical oblivious RAM[END_REF][START_REF] Kantarcioglu | Security issues in querying encrypted data[END_REF][START_REF] Mykletun | Aggregation queries in the database-as-a-service model[END_REF][START_REF] Hacigümüş | Executing SQL over encrypted data in the database-service-provider model[END_REF].

Assumption: b, k Modest. In Sect. 5, we showed that increasing b costs the client more than it costs the colluding servers, so a large b is impractical. With limited resources, we successfully mounted attacks for k = 13 in under 500 seconds, so k must be substantially larger (k > 20) to achieve security in practice. For each server, the client pays a storage cost equal to that of storing his data in plaintext. If k ≥ 10, the combined storage cost exceeds that of many encryptionbased private query techniques [START_REF] Agrawal | Order preserving encryption for numeric data[END_REF][START_REF] Stefanov | Towards practical oblivious RAM[END_REF][START_REF] Mykletun | Aggregation queries in the database-as-a-service model[END_REF], so increasing k is also impractical.

Assumption: Same X, p for Each Secret. Storing a distinct X or prime p on the client for each secret is at least as expensive as storing the secret itself. An alternative is to use a strong, keyed hash h j to generate a distinct vector X = h j (X) for each secret s j . Using this method, each secret requires different basis polynomials for interpolation, so mounting an attack would be much harder. Unfortunately, it also eliminates additive homomorphism, removing support for server-side aggregation, which is cited as a reason for adopting secret sharing.

Assumption: Corresponding Shares can be Aligned. Hiding share order from data servers as in [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF] can hinder share alignment, but if the scheme supports range or point queries, share alignment can eventually be inferred (Sect. 4.3). Schemes could use re-encryption or shuffling to obscure order as in [START_REF] Stefanov | Towards practical oblivious RAM[END_REF], but the cost of such techniques outweighs the performance advantages of secret sharing.

Assumption: k + 2 Known Secrets. It is difficult to keep all secrets hidden from an attacker. Known plaintext/ciphertext attacks for small amounts of data are always a threat, and if we known the real-world distribution of the secrets, we can guess them efficiently (Sect. 4.2). The client could encrypt secrets before sharing, but doing so adds substantial cost and eliminates additive homomorphism.

Related Work

Privacy-preserving data outsourcing was first formalized in [START_REF] Hacigümüş | Executing SQL over encrypted data in the database-service-provider model[END_REF] with the introduction of the Database As a Service model. Since then, many techniques have been proposed to support private querying [START_REF] Agrawal | Order preserving encryption for numeric data[END_REF][START_REF] Stefanov | Towards practical oblivious RAM[END_REF][START_REF] Mykletun | Aggregation queries in the database-as-a-service model[END_REF][START_REF] Ciriani | Keep a few: Outsourcing data while maintaining confidentiality[END_REF][START_REF] Nergiz | Query processing in private data outsourcing using anonymization[END_REF], most based on specialized encryption techniques. For example, order-preserving encryption [START_REF] Agrawal | Order preserving encryption for numeric data[END_REF] supports efficient range queries, while [START_REF] Mykletun | Aggregation queries in the database-as-a-service model[END_REF] supports server-side aggregation through additively homomorphic encryption. Other schemes are based on fragmentation, where only links between sensitive and identifying data are encrypted [START_REF] Ciriani | Keep a few: Outsourcing data while maintaining confidentiality[END_REF][START_REF] Nergiz | Query processing in private data outsourcing using anonymization[END_REF].

As far as we know, the schemes we discuss in this paper [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF][START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF][START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF][START_REF] Agrawal | Database Management as a Service: Challenges and Opportunities[END_REF] are the first to use secret sharing to support private data outsourcing, though secret sharing has been used for related problems, such as cooperative query processing [START_REF] Emekci | Privacy preserving query processing using third parties[END_REF]. Prior works, such as [START_REF] Kantarcioglu | Security issues in querying encrypted data[END_REF], have addressed various security issues surrounding data outsourcing schemes, but as far as we know, ours is the first to reveal the specific limitations of schemes based on secret sharing.

Conclusion

Private data outsourcing schemes based on secret sharing have been advocated because of their slight advantages over existing encryption-based schemes. Such advantages include security, speed, and support for server-side aggregation. All three outsourcing schemes based on secret sharing [START_REF] Hadavi | Secure Data Outsourcing Based on Threshold Secret Sharing; Towards a More Practical Solution[END_REF][START_REF] Agrawal | Secure data management service on cloud computing infrastructures[END_REF][START_REF] Tian | Privacy preserving query processing on secret share based data storage[END_REF] claim that security is maintained even when k or more servers collude. To the contrary, we have shown that all three schemes are highly insecure when k or more servers collude, regardless of whether X and p are kept secret.

We described and implemented an attack that reconstructs all secret data when only k + 2 secrets are known initially. In less than 500 seconds, our attack recovers a hidden 256-bit prime for k ≤ 13 servers, or an 8192-bit prime for k ≤ 8. We discussed possible modifications to mitigate our attack and improve security, but any such modifications sacrifice generality, performance, or functionality.

We conclude that secret sharing outsourcing schemes are not simultaneously secure and practical in the honest-but-curious server model, where servers are not trusted to keep data private. Such schemes should only be used when the client is absolutely confident that at most k -1 servers can collude.

  We do the same with s 2 , s 3 , s 4 (γ = 2) to get δ 2 = -33984:

Fig. 3 .Fig. 4 .

 34 Fig. 3. Riverside dataset times, varied b

Fig. 5 .Fig. 6 .

 56 Fig. 5. Synthetic dataset times, varied b

5 βFig. 7 .

 57 Fig. 7. Attack failure rates for varied k and β

Table

  Fig.1. Secret (salary) data from an employee table is split into shares and distributed to multiple data servers. A trusted client queries shares from the data servers and combines them to recover the secrets.

	ID	Salary
	104	s 1 = 87,650	y 1,1	y 2,1	y 3,1
	751 363 219	s 4 = 20,700 s 3 = 36,425 s 2 = 20,700	y 1,2 y 1,3 y 1,4 …	y 2,2 y 2,3 y 2,4 …	y 3,2 … y 3,4 y 3,3
	840	s 5 = 40,200				Trusted
	Employee	DS 1	DS 2	DS 3	Client

Acknowledgements. This work was supported in part by contract number N00014-07-C-0311 with the Office of Naval Research.


Simon N Foley
email: s.foley@cs.ucc.iewfitzgerald@4c.ucc.ie

William M Fitzgerald

Decentralized Semantic Threat Graphs

Keywords:

Threat knowledge-bases such as those maintained by MITRE and NIST provide a basis with which to mitigate known threats to an enterprise. These centralised knowledge-bases assume a global and uniform level of trust for all threat and countermeasure knowledge. However, in practice these knowledge-bases are composed of threats and countermeasures that originate from a number of threat providers, for example Bugtraq. As a consequence, threat knowledge consumers may only wish to trust knowledge about threats and countermeasures that have been provided by a particular provider or set of providers. In this paper, a trust management approach is taken with respect to threat knowledge-bases. This provides a basis with which to decentralize and delegate trust for knowledge about threats and their mitigation to one or more providers. Threat knowledge-bases are encoded as Semantic Threat Graphs. An ontology-based delegation scheme is proposed to manage trust across a model of distributed Semantic Threat Graph knowledge-bases.

Introduction

Threat management is a process used to help implement a security configuration that mitigates known enterprise (security) threats. Centralised threat knowledgebases, such as NIST's National Vulnerability Database (NVD) [1] are an integral part of the threat management process. However, in practice threat knowledgebases are composed of threats, vulnerabilities and countermeasures that originate from multiple providers, for example US-Cert [2], Bugtraq [3] and/or vendors (such as Cisco and Microsoft). As a consequence, threat knowledge may only be trusted if it has been asserted by a particular provider or set of providers. For example, a consumer of the NVD may only want to trust knowledge about software buffer-overflow vulnerabilities that have been asserted by Bugtraq and corresponding countermeasures asserted by Microsoft. However, access to a centralised threat knowledge-base implies a global or uniform level of trust for all knowledge about threats, vulnerability and countermeasures indiscriminately.

This paper adopts a trust management approach with respect to threat knowledge-bases. The advantages are twofold. The first is that it provides a basis with which a consumer may delegate authority to trusted providers for knowledge about threats, vulnerabilities and countermeasures. Secondly, it provides a basis to decentralize a threat knowledge-base where trusted threat knowledge may reside with the originating provider and/or be distributed across other trusted provider threat knowledge-bases.

Threat Trees/Graphs, such as [START_REF] Foley | Management of Security Policy Configuration using a Semantic Threat Graph Approach[END_REF][START_REF] Ray | Using Attack Trees to Identify Malicious Attacks from Authorized Insiders[END_REF][START_REF] Schneier | Secrets and Lies Digital Security in Networked World[END_REF], are used to represent, structure and analyse what is known about threats and their countermeasures. In this paper, threat knowledge-bases are encoded as Semantic Threat Graphs [START_REF] Foley | Management of Security Policy Configuration using a Semantic Threat Graph Approach[END_REF]. We argue that using an ontology-based framework provides a natural approach to constructing, reasoning about and managing decentralized Semantic Threat Graphs. An ontology provides a conceptual model of a domain of interest. It provides a framework for distributed and extensible structured knowledge founded on formal logic [START_REF] Baader | The Description Logic Handbook: Theory, Implementation and Applications[END_REF]. In recent years, research in computer security has seen an increase in the use of ontologies. For example, ontologies have been applied to the areas of information security (common security vocabulary) [START_REF] Herzog | An Ontology of Information Security[END_REF], security management (threats, vulnerabilities and countermeasures) [START_REF] Fenz | Information Security Fortification by Ontological Mapping of the ISOIEC 27001 Standard[END_REF], access control [START_REF] Cuppens-Boulahia | An Ontology-Based Approach to React to Network Attacks[END_REF], policy management [START_REF] Kodeswaran | Enforcing Security in Semantics Driven Policy Based Networks[END_REF] and trust management [START_REF] Thuraisingham | Building Trustworthy Semantic Webs[END_REF]. The decentralized Semantic Threat Graphs (ontology fragments) are implemented in OWL-DL, a language subset of OWL which is a W3C standard that includes Description Logic reasoning semantics [START_REF] Smith | OWL Web Ontology Language Guide[END_REF].

Distributed fragments of Semantic Threat Graphs that are naturally composable under the open-world assumption, provide a unified view of the threat-based domain. Ontologies provide for separation of concerns, whereby consumers and providers of threat-based knowledge can be separately developed, with reasoning and deployment over their composition done locally. It also means that information about new threats, vulnerabilities and countermeasures can be incorporated as new facts within existing Semantic Threat Graph knowledge-bases.

The paper is outlined as follows. Section 2 provides an overview of Description Logic. Section 3 outlines the Semantic Threat Graphs model and an encoding of standards of best practice for threat mitigation. Section 4 describes the delegation scheme used to manage trust across a model of distributed threat knowledge-bases. A model for decentralized Semantic Threat Graphs is presented in Section 5. Section 6 provides use case scenarios that demonstrate how the approach may work in practice. Related research is discussed in Section 7.

Description Logic and Knowledge-Bases

The Description Logic SHOIN (D) is a decidable portion of First Order Logic that can be used to represent and reason about application knowledge and is commonly implemented as OWL-DL [START_REF] Baader | The Description Logic Handbook: Theory, Implementation and Applications[END_REF]. Knowledge is described in terms of concepts about individuals and their relationships. For example, suppose that concept DOS describes denial of service threats and concept TCPcntr describes TCP-stack based countermeasures such as syn-cookie and syn-cache, then the concept (∃ 1 mitigates.DOS) ⊓ TCPcntr can be considered to characterize TCPcntr countermeasure concepts that mitigate denial of service threats. In this case mitigates is a property that has been defined between DOS threats and countermeasures. For example, the individual countermeasure syn-cache is related (property mitigates) to the individual DOS threat syn-flood. A Description Logic concept corresponds to a unary predicate; intuitively, it represents a set, and concept conjunction (⊓) and disjunction (⊔) provide set intersection and union, respectively. A Description Logic property (role) corresponds to a binary predicate. The concept (∃ ≥1 p.φ) defines individuals related to at least one individual of concept φ via property p.

A knowledge-base comprises a terminological component, hereafter referred to as its TBox, and an assertional component (its ABox ). In addition to describing concepts, a TBox may define concept and property relationships. These are given as axioms of the form φ 1 ⊑ φ 2 , given concepts φ 1 and φ 2 and where subsumption ⊑ can be interpreted as subset. For example, the TBox containing the concepts from the previous paragraph could include the axiom DOS ⊑ Threat, indicating that denial of service is a kind of threat. Property subsumption axioms may similarly be defined, which we also represent as φ 1 ⊑ φ 2 if no ambiguity arises.

Semantic Threat Graphs

Semantic Threat Graphs [START_REF] Foley | Management of Security Policy Configuration using a Semantic Threat Graph Approach[END_REF], a variation of the traditional Threat/Attack Tree, are encoded within an ontology-based framework. Figure 1 provides an abstract model for Semantic Threat Graphs and identifies the key concepts and relationships.

Enterprise IT assets are represented as individuals of the Asset concept. An asset may have one or more hasWeakness's (property relationship) that relate to individuals categorised in the Vulnerability concept. Individuals of the Vulnerability concept are exploitable (exploitedBy) by a threat or set of threats (Threat concept). As a consequence, an asset that has a vulnerability is, therefore, also threatenedBy a corresponding Threat. A countermeasure mitigates particular vulnerabilities. Countermeasures are deemed to be kinds-of assets and thus are defined as a subConceptOf Asset.

Semantic Threat Graphs can be used to encode standards and best practices for threat mitigation using firewalls [START_REF] Foley | Management of Security Policy Configuration using a Semantic Threat Graph Approach[END_REF]. Mis-configured firewall security configurations have the potential to expose both internal servers and the firewalls themselves to threats. For example, consider the following scenario where a webServer is susceptible to a threat SynFlood attack via the vul WebTCPConnOverflow weakness. An individual vul WebTCPConnOverflow is representative of a weakness in the TCP stack where it is possible exceed the maximum number of socket connections permitted by the TCP protocol due to a syn flood attack [START_REF] Stevens | Unix Network Programming, Networking API's: Sockets and XTI[END_REF]. An iptables rule, represented as individual iptr SynThresholdWeb , mitigates the vulnerability vul WebTCPConnOverflow on the Web server (webServer). Note that we use humaninterpretable names (in a typewriter font) for individuals in the ontology as a way of suggesting their meaning. For example, individual iptr SynThresholdWeb represents an iptables rule (iptr) that limits TCP syn packet connections to the Web server (SynThresholdWeb). The Semantic Threat Graph model presented in Figure 1 can be further refined with sub-concepts. For example, the Threat concept can define a number of sub-concepts in accordance with best practice, such as the Microsoft STRIDE standard whereby threats are categorised as (Figure 2): Spoofing identity, Tampering with data, Repudiation, Information disclosure, Denial of service and Elevation of privilege [START_REF] Hernan | Uncover Security Design Flaws Using The STRIDE Approach[END_REF]. A similar hierarchy is adopted for the corresponding vulnerability and countermeasure concepts. A best practice standard is a high-level document, written in natural language (typically English text), that defines a set of recommended best practices (countermeasures) to protect sensitive and critical system resources. Best practice standards for network access control, including NIST for secure Web-servers [START_REF] Tracy | Guidelines on Securing Public Web Servers: Recommendations of the National Institute of Standards and Technology[END_REF] and Internet RFCs for anti-bogon (RFC3330) are encoded as Semantic Threat Graphs (ontologies). How these best practice standards are encoded in terms of Semantic Threat Graphs is described in [START_REF] Foley | Management of Security Policy Configuration using a Semantic Threat Graph Approach[END_REF]. For example, Table 1 provides a Semantic Threat Graph interpretation for part of the NIST-800-41 standard [START_REF] Wack | Guidelines on Firewalls and Firewall Policy: Recommendations of the National Institute of Standards and Technology[END_REF] for firewall configuration. FBP-1 recommends that (spoofed) packets arriving on an external interface claiming to have originated from either of the three RFC1918 reserved internal IP address ranges should be dropped. Such traffic indicates a denial of service attack typically involving the TCP syn flag. Therefore, T hreat individual threat Inbound192.168.0.0/16SrcIPPkt , is asserted to be a member of subconcepts Spoofing, DenialOfService and RF C1918T hreat. Figure 2 illustrates a partial hierarchy of threats.

ID Recommendation Description

FBP-1 Deny "Inbound or Outbound traffic from a system using a source address that falls within the address ranges set aside in RFC1918 as being reserved for private networks" [START_REF] Wack | Guidelines on Firewalls and Firewall Policy: Recommendations of the National Institute of Standards and Technology[END_REF].

Threat

Knowledge Delegation as Subsumption

A (distributed) system may comprise of a number of separately managed knowledge bases. Each knowledge-base is assumed to have a unique name that indicates its controlling/owning principal. We assume that each atomic concept (or property) φ syntactically embeds the name (φ) N of the principal that describes the concept (or property). For example, a TBox owned by principal A includes a concept A:DOS where (A:DOS) N = A. A principal P has jurisdiction over any concept (or property) φ if (φ) N = P ; this means that P is considered to be the original authority on φ.

Note that while a TBox may contain concepts originating from different principals, all concepts referenced in a concept expression are required to have the same name. For example, (A:Threat ⊓ A:DOS) N = A. This ensures a consistent interpretation for our syntatic approach to referencing (the originator of) concepts. Future research will consider how a permission-naming logic such as [START_REF] Foley | Avoiding delegation subterfuge using linked local permission names[END_REF] can be used to provide a consistent treatment for the originators of a concept such as (A:Threat ⊓ B:DOS).

Principals may make public assertions about terminological knowledge. A public assertion P | ≈(φ 1 ⊑ φ 2 ) is a statement by principal P about concept (or property) subsumption. For example, A | ≈(B:DOS ⊑ A:Threat) is an assertion by A that its concept of threat includes B's concept of denial of service. These ontology mappings can be used to implement delegation of jurisdiction. Given (φ 1 ) N = Q and (φ 2 ) N = P then P | ≈(φ 1 ⊑ φ 2 ) is an assertion by P that it trusts Q when it describes φ 1 to the extent that Q's concept of φ 1 can be considered as a kind of φ 2 concept over which P 's has jurisdiction. For example, suppose that principal B provides a vulnerability reporting service, then assertions A | ≈(B:DOS ⊑ A:DOS) and A | ≈(B:mitigates ⊑ A:mitigates) mean that A trusts B's mitigation knowledge for denial of service attacks.

Transitive subsumption in SHOIN (D) can be used to reason over chains of delegation statements. For example, public assertion B | ≈(C:mitigates ⊑ B:mitigates) indicates that the vulnerability reporting service B trusts mitigation recommendations provided by a software developer C. Continuing the example, principal A can use these public assertions to deduce that C:mitigates ⊑ A:mitigates and thus be happy to trust mitigation recommendations from the software developer.

The following rule defines the conditions under which an arbitrary principal may import, into its TBox, a public assertion (delegation) from P .

P | ≈(φ 1 ⊑ φ 2 ); (φ 2 ) N = P import φ 1 ⊑ φ 2 into TBox
This does not extend the semantics of SHOIN (D) , rather, it is a syntactic treatment whereby delegation statements translate to concept axioms that can in turn be reasoned over within SHOIN (D) . This treatment is easily modeled within OWL-DL. The URI of an OWL-DL document provides its principal/namespace. A public assertion P | ≈(φ 1 ⊑ φ 2 ) is an ontology document that is trusted to originate from the namespace of P : this trust can be achieved by P signing the document. The ontology-import constructor owl:imports is used to import a public assertion that is confirmed to come from a from another namespace.

The assertional component of a knowledge base, hereafter referred to as its ABox, contains assertions about named concept individuals. A concept assertion φ(i), indicates that named individual i is a member of concept φ; a role (property) assertion p(i, j) indicates that named individual i is related to named individual j under property p. For example, ABox assertion DOS(syn-flood) describes that individual syn-flood is a DOS threat and ABox role assertion mitigates(syn-cache,syn-flood) describes that the syn-cache countermeasure mitigates a syn-flood threat.

We use a similar naming scheme for individuals whereby (i) N indicates a principal/namespace syntactically embedded in the identifier of the individual i. Principals may make public assertions about individuals. A public assertion P | ∼ φ(i) is a statement by P that named individual i is a member of concept φ. A principal may not make public assertions about ABox knowledge (concept and individual) that is not under its jurisdiction. However, a principal may use subsumption to infer ABox knowledge that is effectively under the jurisdiction of others. The following rule defines the conditions under which an arbitrary principal may import, into its ABox, a public assertion from P about a named individual i and concept φ.

P | ∼ φ(i); (φ) N = (i) N = P import φ(i) into ABox
A similar rule can be defined for public ABox property assertions.

Continuing the above example, B | ∼(B:DOS(B:syn-flood)) is a statement by the vulnerability reporting service B that B:syn-flood is a B:DOS threat. On importing this ABox assertion and the TBox assertion A | ≈(B:DOS ⊑ A:DOS), it is possible for A to deduce A:DOS(B:syn-flood), that is, B:syn-flood is an A:DOS threat.

These public ABox assertions are a syntactic treatment that do not extend SHOIN (D) . In practice, OWL-DL individuals include reference to their namespace (principal) and a public ABox assertion P | ∼ φ(i) is an ontology document that has been signed by its originator P and a valid φ(i) can be imported into another ontology using the owl:imports constructor.

In general, a public TBox assertion P | ≈(φ 1 ⊑ φ 2 ) is effectively a delegation certificate that can be understood as a statement P | ≈(φ 2 ⊃ φ 1 ) in a delegation logic such as [START_REF] Abadi | A calculus for access control in distributed systems[END_REF], where φ 1 and φ 2 are unary (or binary) predicates that refer to static principals (φ 1 ) N and (φ 2 ) N , respectively. A public ABox assertion P | ∼ φ(i) is a signed value of type φ that can be effectively considered to be a form of a signed permission that cannot be forged by another principal that does not hold jurisdiction.

Note that for ease of presentation, delegation of trust is assumed transitive. Non-transitive trust can be incorporated into the model, for example, by adding a SPKI-style [START_REF] Ellison | SPKI certificate theory[END_REF] delegation-bit to delegation certificates. Alternatively, a KeyNote-style [START_REF] Blaze | The keynote trustmanagement system[END_REF] Action Authorizers concept could be added to the ontology to constrain the delegation.

Delegation in Semantic Threat Graphs

A decentralized Semantic Threat Graph (STG) uses subsumption to model the delegation of jurisdiction over (potentially distributed) fragments of a Semantic Threat Graph. These fragments can include concepts such as V ulnerability, T hreat and Countermeasure, assertions about membership of these concepts and assertions about properties between the concepts. In this section, we outline how the delegation involving these fragments is encoded using subsumption; Section 6 will provide complete examples of decentralized Semantic Threat Graphs. STG Concept Delegation. Subsumption is used to define delegation of T hreat, V ulnerability and Countermeasure concepts between principals. For example, Y | ≈ X : DenialOfService ⊑ Y : T hreat defines that principal Y trusts principal X, concerning the identification (naming) of denial of service attacks. Suppose that X in turn asserts X | ∼ X : DenialOfService(X : threat SynFlood ) that is, X : threat SynFlood is a DenialOfService individual, as identified by X. In this case, as a result of the delegation by subsumption above, principal Y can safely deduce that Y : Threat(X : threat SynFlood ) that is, X : threat SynFlood can be identified as an individual of Y 's Threat concept. Similar assertions can be made about other Semantic Threat concepts including V ulnerability and Countermeasure.

STG Property Delegation. Like concepts, properties can be hierarchical, and over which, principals may make jurisdiction assertions. For example, the property delegation Y | ≈ X : exploits ⊑ Y : exploits is a statement by Y that it is willing to trust properties from the knowledgebase of X that relate how vulnerabilities are exploited by threats. For example, suppose that principal X asserts X | ∼ X : exploits(X : threat SynFlood , X : vul WebTCPConnMax ) then principal Y , trusting X's assertions on exploits (X : exploits ⊑ Y : exploits) can infer the following statements in its knowledge base.

Y : Threat(X : threat SynFlood ), Y : Vulnerability(X : vul WebTCPConnMax ), Y : exploits(X : threat SynFlood , X : vul WebTCPConnMax )

STG Property Restriction Delegation. Restrictions ('quantifier' and 'hasValue') can be applied to properties and are used to constrain an individual's membership to a specific concept. A property restriction effectively describes an anonymous or unnamed concept that contains all the individuals that satisfy the restriction. For example, principal Y asserts

Y | ≈(∃ ≥1 X : exploits.X : V ulnerability ⊑ Y : T hreat)
meaning that threat individuals that are members of an unnamed threat concept ∃ ≥1 X : exploits.X : V ulnerability defined within principal X's knowledge-base are considered as trusted individuals of concept Y : T hreat in principal Y 's knowledge-base. A 'hasValue' restriction, denoted by ∋, describes a set of individuals that are members of an anonymous concept (domain) that are related to a specific individual along the range of a given property. For example, in Y | ≈ X : exploits ∋ X : vul WebTCPConnMax ⊑ Y : T hreat Y asserts that it trusts principal X's knowledge about threats that exploit the X : vul WebTCPConnMax . Therefore, threat is X : threat SynFlood is considered a threat (a member of concept Y : T hreat) within principal Y 's knowledgebase. Note, concept X : exploits ∋ X : vul WebTCPConnMax is a sub-concept of the ∃ ≥1 X : exploits.X : V ulnerability.

Decentralized Semantic Threat Graphs: Use Cases

In this section, a series of examples are presented in order to demonstrate how decentralized Semantic Threat Graphs may work in practice and in which we identify some potential business usage patterns (Figure 3). We believe this to be an improvement over the current centralised approach where trust between different providers is not discriminated.

Knowledge about threats, vulnerabilities and countermeasures while originating from a number of providers, is typically managed within centralised threat knowledge-bases such as NIST's National Vulnerability Database (NVD) [1]. The advantage of decentralising a threat knowledge-base means that threat knowledge may reside with the originating provider and/or be distributed across other trusted third party providers. A disadvantage of a centralised approach is that it implies on the part of a consumer a global level of trust for all threat knowledge indiscriminately. However, a consumer may only wish to trust threat knowledge that has been provided by a particular provider or set of providers. For example, a consumer of the NVD may only want to trust knowledge about network-based Denial of Service threats that have been provided by US-Cert and corresponding (firewall) countermeasures provided by Redhat. The advantage of a trust management approach is that it provides a basis with which a consumer may delegate authority to trusted providers for threat knowledge. In practice, providers/producers construct fragments of Semantic Threat Graphs and consumers make assertions about the conditions under which they trust the fragments provided by providers. These are defined as a combination of STG Concept, Property and Property Restriction delegation assertions described in the previous section.

Use Case 1. A company (for example, ACME Inc.) having a consumer role, delegates jurisdiction for knowledge about threats, vulnerabilities and countermeasures to one or more trusted compliance agencies (for example, NIST) having a role of a provider. A compliance agency, having a consumer role in this instance, in turn delegates jurisdiction for knowledge about threats, vulnerabilities and countermeasures to one or more trusted vendors (for example Redhat). A vendor (provider) may then notify the company with respect to Semantic Threat Graph knowledge it has jurisdiction over. The company can import these STG assertions into its knowledge-base and use the knowledge during reasoning. For indicating that it trusts countermeasure recommendations made by NIST regarding threats and vulnerabilities that are to be mitigated in order to be be compliant with NIST-800-41 [START_REF] Wack | Guidelines on Firewalls and Firewall Policy: Recommendations of the National Institute of Standards and Technology[END_REF] firewall best practice. Note that, when no ambiguity can arise, we drop the turnstile notation "| ≈" and "| ∼" and infer the principal from the statement.

Principal NIST, in turn, asserts: Redhat. Note, the delegation statement made by NIST also includes additional knowledge about its threat and vulnerability hierarchy. For example concept NIST : Spoofing is a subsumed by concept NIST : NIST80041Threat. Delegation chains (transitive subsumption) constructed in terms of concept and property subsumption can be reasoned over within OWL-DL to establish if received ABox statements are to be trusted and imported. For example, Redhat (principal RH) asserts the following anti-bogon IP spoofing threat information:

NIST
RH :

Related Research

The delegation scheme proposed in this paper is based on managing trust across a model of distributed knowledge-bases. While the model is simple, it closely resembles the OWL-DL approach to modular ontologies [START_REF] Grau | Modular Resuse of Ontologies: Theory and Practice[END_REF] using the owl:imports constructor with a URI based namespace. Future research will explore representing and reasoning about distributed trust in other modular Description Logic languages such as [START_REF] Borgida | Distributed Description Logics: Directed Domain Correspondences in Federated Information Sources. On The Move to Meaningful Internet Systems[END_REF][START_REF] Wang | A survey of formalisms for modular ontologies[END_REF]. The TBox intensional reasoning provided by existing OWL-DL reasoners is relatively scalable, however, extensional reasoning is poor for medium to large-sized ABoxes.

A large body of research results exist on Trust Management and decentralized authorization systems, for example, [START_REF] Becker | Design and semantics of a decentralized authorization language[END_REF][START_REF] Blaze | Decentralized trust management[END_REF][START_REF] Ellison | SPKI certificate theory[END_REF][START_REF] Li | Distributed credential chain discovery in trustmanagement[END_REF]. However, there has been little consideration regarding how it might be applied to managing trust relationships across knowledge-bases, which is considered in this paper. In [START_REF] Squicciarini | Achieving Privacy in Trust Negotiations with an Ontology-Based Approach[END_REF], a centralised reference ontology is developed to represent trust requirements. Agarwal and Rudolph [START_REF] Agarwal | Semantic Description of Behavior and Trustworthy Credentials of Web Services[END_REF] present an ontology for SPKI/SDSI certificates. In [START_REF] Agarwal | Semantic Description of Behavior and Trustworthy Credentials of Web Services[END_REF] SPKI names are represented as concept names while public keys are represented as individuals. However, once the ontology is constructed any reasoning over delegation chains for the purpose of compliance checking is performed outside of the ontology framework.

Trust Management systems typically describe policy and authorization in terms of discrete permissions and/or assertions. In this paper, authority (about STGs) is defined in terms of Description Logic concepts. Description Logic has been used to describe and reason about RBAC [START_REF] Finin | ROWLBAC -Representing Role Based Access Control in OWL[END_REF] and XACML policies [START_REF] Kolovski | Analyzing web access control policies[END_REF] with subsumption providing role/authorization hierarchies, but do not consider the jurisdiction that principals may have over the ontologies in their local knowledgebases. Semantic SPKI [START_REF] Agudo | Enabling attribute delegation in ubiquitous environments[END_REF] uses subsumption to define SDSI local name bindings, however an external certificate discovery algorithm implements name reduction. In our paper, public keys are used to uniquely identify principals and their name spaces. Future work will extend this to support SDSI naming, based on the logic described in [START_REF] Foley | Avoiding delegation subterfuge using linked local permission names[END_REF].

The requirements of Distributed Semantic Threat Graphs determined our particular use of Trust Management and effectively corresponds to a conventional compliance check [START_REF] Blaze | Decentralized trust management[END_REF]: for a given delegation network, is a principal trusted for some action? This check returns a binary answer and we believe that the model could be extended to support forms of quantitative trust, by incorporating KeyNote-style [START_REF] Blaze | The keynote trustmanagement system[END_REF] compliance values or weights [START_REF] Bistarelli | A semantic foundation for trust management languages with weights: An application to the rt family[END_REF][START_REF] Foley | Aggregating trust using triangular norms in the keynote trust management system[END_REF] in the delegation statements. We also assume that trust is monotonic, for example, it is safe to rely on a Semantic Threat Graph delegation chain provided by a vendor since the model does not permit other principals to make conflicting assertions about concepts that originated from the vendor's namespace. Supporting non-monotonic trust, including inter-policy-conflicts such as [START_REF] Bertino | Supporting multiple access control policies in database systems[END_REF], is non-trivial and effectively requires synchronization of the distributed ABox/TBoxes. Providing support for distributed ontologies is an active research topic [START_REF] Bao | Modular ontologies. chap. Package-Based Description Logics[END_REF]. The extent to which these other forms of reasoning over the distributed ontology are applicable, and could be supported by extending our current model, is a topic for future research.

Conclusion

In this paper, a trust management approach is proposed to decentralize and delegate knowledge for threats and their mitigation (encoded as Semantic Threat Graphs) to one or more trusted providers. That is, the ability to trust-manage the (delegation) relationships that may exist between the providers.

The ontology-based delegation scheme used subsumption to model the delegation of jurisdiction over (potentially distributed) fragments of a Semantic Threat Graph. This paper extends the model from [START_REF] Foley | Management of Security Policy Configuration using a Semantic Threat Graph Approach[END_REF] -which did not consider the possibility that threat catalogues may originate from different trusted providers -to a decentralized trust model.

In this paper, the Semantic Threat Graphs knowledge-bases comprised of knowledge about standards and best practices for threat mitigation using firewalls. The applicability of the (centralised) approach of encoding numerous bestpractices is demonstrated in [START_REF] Foley | Management of Security Policy Configuration using a Semantic Threat Graph Approach[END_REF]. We argue that the effort of decentralizing this cataloging exercise is comparable. Future work will consider constructing Semantic Threat Graphs from additional threat knowledge-bases such as NVD.

Fig. 1 .

 1 Fig. 1. Abstract Semantic Threat Graph Model.

  Vulnerability Countermeasure threatInbound192.168.0.0/16SrcIPPkt vulUnAuthenInbound192.168.0.0/16PktToFW iptrDropIn192.168.0.0/16SrcIPPktInputChain threatOutbound192.168.0.0/16SrcIPPktvulUnAuthenOutbound192.168.0.0/16PktFromFW iptrDropOut192.168.0.0/16SrcIPPktOutputChain threatInbound192.168.0.0/16SrcIPPkt vulUnAuthenInbound192.168.0.0/16PktToHost iptrDropIn192.168.0.0/16SrcIPPktForwardChain threatOutbound192.168.0.0/16SrcIPPktvulUnAuthenOutbound192.168.0.0/16PktFromHostiptrDropOut192.168.0.0/16SrcIPPktForwardChain threatInbound10.0.0.0/8SrcIPPkt vulUnAuthenInbound10.0.0.0/8PktToFW iptrDropIn10.0.0.0/8SrcIPPktInputChain threatOutbound10.0.0.0/8SrcIPPkt vulUnAuthenOutbound10.0.0.0/8PktFromFW iptrDropOut10.0.0.0/8SrcIPPktOutputChain threatInbound10.0.0.0/8SrcIPPkt vulUnAuthenInbound10.0.0.0/8PktToHost iptrDropIn10.0.0.0/8SrcIPPktForwardChain threatOutbound10.0.0.0/8SrcIPPkt vulUnAuthenOutbound10.0.0.0/8PktFromHost iptrDropOut10.0.0.0/8SrcIPPktForwardChain threatInbound172.16.0.0/12SrcIPPkt vulUnAuthenInbound172.16.0.0/12PktToFW iptrDropIn172.16.0.0/12SrcIPPktInputChain threatOutbound172.16.0.0/12SrcIPPkt vulUnAuthenOutbound172.16.0.0/12PktFromFW iptrDropOut172.16.0.0/12SrcIPPktOutputChain threatInbound172.16.0.0/12SrcIPPkt vulUnAuthenInbound172.16.0.0/12PktToHost iptrDropIn172.16.0.0/12SrcIPPktForwardChain threatOutbound172.16.0.0/12SrcIPPkt vulUnAuthenOutbound172.16.0.0/12PktFromHost iptrDropOut172.16.0.0/12SrcIPPktForwardChain ID Recommendation Description FBP-2 Deny "Inbound traffic containing ICMP (Internet Control Message Protocol) traffic" [35].

Fig. 3 .

 3 Fig. 3. Example Delegation Usage Patterns.

:

  Spoofing ⊑ NIST : NIST80041Threat NIST : UnAuthPkt ⊑ NIST : NIST80041Vulnerability RH : Spoofing ⊑ NIST : Spoofing RH : UnAuthPkt ⊑ NIST : UnAuthPkt RH : IptablesRule ⊑ NIST : NIST80041Countermeasure RH : exploits ⊑ NIST : exploits RH : mitigates ⊑ NIST : mitigates indicating that principal RH (Redhat vendor) is trusted to specify Linux iptables firewall countermeasures used to mitigate spoofing threats and associated vulnerabilities. Intuitively, the NIST compliance agency has outsourced the instantiation of spoof-based threats and recommended firewall countermeasures to

Table 1 .

 1 Ontology

Extract for NIST-800-41: Guidelines on Firewalls & Firewall Policy.

  Spoofing(RH : threat Inbound192.168.0.0/16SrcIPPkt ), RH : UnAuthPkt(RH : vul UnAuthenInbound192.168.0.0/16PktToHost ), RH : IptablesRule(RH : iptr DropIn192.168.0.0/16SrcIPPktForwardChain ), RH : exploits(RH : threat Inbound192.168.0.0/16SrcIPPkt , RH : vul UnAuthenInbound192.168.0.0/16PktToHost ), RH : mitigates(RH : iptr DropIn192.168.0.0/16SrcIPPktForwardChain , RH : vul UnAuthenInbound192.168.0.0/16PktToHost ) On receipt of this ABox statement principal ACME has no prior trust relationship with RH. However, given the set of known delegation statements, ACME can form the following delegation (trust) chains. ACME can deduce that the ABox mitigation knowledge received from RH is trusted. It then becomes possible for ACME to deduce a new concept hierarchy within its local Semantic Threat Graph knowledge-base, for example: more vendors such as Redhat or Cisco, it may instead decide to delegate certain fragments (for example threats) to one or more additional compliance agencies and other fragments (for example countermeasures) to one or more vendors. Vendors in turn may also trust one or more compliance agencies. In this example, ACME makes the same TBox statement for delegation of jurisdiction to NIST defined in the previous scenario. Principal NIST delegates jurisdiction to CVE (compliance agency) for knowledge about NIST-800-41 spoofing threats and vulnerabilities only. NIST : Spoofing ⊑ NIST : NIST80041Threat NIST : UnAuthPkt ⊑ NIST : NIST80041Vulnerability CVE : Spoofing ⊑ NIST : Spoofing CVE : UnAuthPkt ⊑ NIST : UnAuthPkt CVE : exploits ⊑ NIST : exploits Principal NIST also asserts the following delegation statement stating that principal RH is trusted for NIST-800-41 based iptables firewall countermeasures. RH : iptablesRule ⊑ NIST : NIST80041Countermeasure RH : mitigates ⊑ NIST : mitigates Note, trust is not bidirectional. Given that RH has not been given jurisdiction over relevant threats and vulnerabilities with which to make iptables recommendations, it must also delegate jurisdiction to NIST for this knowledge. Spoofing(CVE : threat Inbound192.168.0.0/16SrcIPPkt ), CVE : UnAuthPkt(CV E : vul UnAuthenInbound192.168.0.0/16PktToHost ), CVE : exploits(CV E : threat Inbound192.168.0.0/16SrcIPPkt , CVE : vul UnAuthenInbound192.168.0.0/16PktToHost ) Principal RH can form a chain of trust based on its trust for NIST and NIST's trust for CVE. As a consequence, RH can define a suitable iptables rule (countermeasure) that mitigates the vulnerability of unauthenticated 192.168.0.0/16 subnet packets exploited by spoofed packets of the same source IP range. Principal ACME in turn receives the following ABox statements from RH for which it has no prior trust relationship. RH : Spoofing(CVE : threat Inbound192.168.0.0/16SrcIPPkt ), RH : UnAuthPkt(CVE : vul UnAuthenInbound192.168.0.0/16PktToHost ), RH : IptablesRule(RH : iptr DropIn192.168.0.0/16SrcIPPktForwardChain ), RH : exploits(CVE : threat Inbound192.168.0.0/16SrcIPPkt , CVE : vul UnAuthenInbound192.168.0.0/16PktToHost ), RH : mitigates(RH : iptr DropIn192.168.0.0/16SrcIPPktForwardChain , CVE : vul UnAuthenInbound192.168.0.0/16PktToHost ) Principal ACME can form a chain of trust based on its trust for NIST and NIST's trust for CVE and RH. For example: CVE : Spoofing ⊑ NIST : Spoofing ⊑ NIST : NIST80041Threat ⊑ ACME : Threat CVE : UnAuthPkt ⊑ NIST : UnAuthPkt ⊑ NIST : NIST80041Vul ⊑ ACME : Vulnerability RH : IptablesRule ⊑ NIST : NIST80041Countermeasure ⊑ ACME : Countermeasure Use Case 3. This scenario is a variation of use case 2. A company may trust one or more vendors for Semantic Threat Graph ABox statements where each vendor may in turn trust other vendors and/or compliance agencies for ABox Semantic Threat Graph statements. For reasons of space, we do not provide example TBox delegation statements and Abox statements.

	to one or NIST : Spoofing ⊑ RH : Spoofing
	NIST : UnAuthPkt ⊑ RH : UnAuthPkt
	NIST : exploits ⊑ RH : exploits
	Principal RH receives the following ABox statements from CVE for which it
	in addition to the following inferred concept membership and property relations: has no prior trust relationship.
	ACME : Threat(RH : threat Inbound192.168.0.0/16SrcIPPkt ),
	ACME : Vulnerability(RH : vul UnAuthenInbound192.168.0.0/16PktToHost ),
	ACME : Countermeasure(RH : iptr DropIn192.168.0.0/16SrcIPPktForwardChain ),
	ACME : exploits(RH : threat Inbound192.168.0.0/16SrcIPPkt ,
	RH : vul UnAuthenInbound192.168.0.0/16PktToHost ),
	ACME : mitigates(RH : iptr DropIn192.168.0.0/16SrcIPPktForwardChain ,
	RH : vul UnAuthenInbound192.168.0.0/16PktToHost )
	Use Case 2. As in the previous use case, a company may delegate jurisdiction
	for knowledge about threats, vulnerabilities and countermeasures to one or more RH : IptablesRule(RH : iptr DropIn192.168.0.0/16SrcIPPktForwardChain ),
	trusted compliance agencies. However, rather than a compliance agency delegat-RH : mitigates(RH : iptr DropIn192.168.0.0/16SrcIPPktForwardChain ,
	ing jurisdiction over threats, vulnerabilities and countermeasures as a collection CVE : vul UnAuthenInbound192.168.0.0/16PktToHost )

RH : Spoofing ⊑ NIST : Spoofing ⊑ NIST : NIST80041Threat ⊑ ACME : Threat RH : UnAuthPkt ⊑ NIST : UnAuthPkt ⊑ NIST : NIST80041Vul ⊑ ACME : Vulnerability RH : IptablesRule ⊑ NIST : NIST80041Countermeasure ⊑ ACME : Countermeasure RH : exploits ⊑ NIST : exploits ⊑ ACME : exploits RH : mitigates ⊑ NIST : mitigates ⊑ ACME : exploits As a consequence, RH : Spoofing ⊑ NIST : Spoofing ⊑ NIST : NIST80041Threat ⊑ ACME : Threat CVE :

Acknowledgements. The authors would like to thank the anonymous reviewers for their valuable feedback. This research has been supported by Science Foundation Ireland grant 08/SRC/11403.