# Multiple Run Ensemble Learning with Low-Dimensional Knowledge Graph
Embeddings

Chengjin Xu1, Mojtaba Nayyeri1, Sahar Vahdati2 and Jens Lehmann13  1SDA
Research, University of Bonn, Bonn, Germany
Email: {xuc, nayyeri<EMAIL_ADDRESS>2University of Oxford,
Oxford, UK
Email<EMAIL_ADDRESS>3Fraunhofer IAIS, Bonn, Germany
Email<EMAIL_ADDRESS>
###### Abstract

Knowledge graphs (KGs) represent world facts in a structured form. Although
knowledge graphs are quantitatively huge and consist of millions of triples,
the coverage is still only a small fraction of world’s knowledge. Among the
top approaches of recent years, link prediction using knowledge graph
embedding (KGE) models has gained significant attention for knowledge graph
completion. Various embedding models have been proposed so far, among which,
some recent KGE models obtain state-of-the-art performance on link prediction
tasks by using embeddings with a high dimension (e.g. 1000) which accelerate
the costs of training and evaluation considering the large scale of KGs. In
this paper, we propose a simple but effective performance boosting strategy
for KGE models by using multiple low dimensions in different repetition rounds
of the same model. For example, instead of training a model one time with a
large embedding size of 1200, we repeat the training of the model 6 times in
parallel with an embedding size of 200 and then combine the 6 separate models
for testing while the overall numbers of adjustable parameters are same
(6*200=1200) and the total memory footprint remains the same. We show that our
approach enables different models to better cope with their expressiveness
issues on modeling various graph patterns such as symmetric, 1-n, n-1 and n-n.
In order to justify our findings, we conduct experiments on various KGE
models. Experimental results on standard benchmark datasets, namely FB15K,
FB15K-237 and WN18RR, show that multiple low-dimensional models of the same
kind outperform the corresponding single high-dimensional models on link
prediction in a certain range and have advantages in training efficiency by
using parallel training while the overall numbers of adjustable parameters are
same.

###### Index Terms:

Graph Embedding, Ensemble Learning, Statistical Relational Learning, Link
Prediction

##  I Introduction

Numerous knowledge graphs including lexical datasets and world’s knowledge,
such as WordNet [1], FreeBase [2], YAGO [3], and DBpedia [4], have been
published with different utilization purposes. These KGs have become a
significant resource for many AI-based applications such as question answering
and recommendation systems [5]. Therefore, a new horizon for using machine
learning approaches on structured data at scale has been opened up for leading
science and industry.

Despite all the advantages of KGs in down stream tasks, one of the main
challenges of existing KGs is their incompleteness [6]. Knowledge graph
completion using link prediction approaches aims at addressing the
incompleteness of KGs. Among various link prediction approaches, knowledge
graph embedding (KGE) has gained significant attention recently. A KGE model
takes a KG in the form of triple facts $(h,r,t)$ where $h,t$ are entities
(nodes) and $r$ is a relation (link) between the entities (e.g. (Berlin,
Capital_of, Germany)). A vector is assigned to each element of a triple
($\mathbf{h},\mathbf{r},\mathbf{t}$) in a KG and all vectors are then adjusted
by optimizing a loss function. The likelihood of a triple is then measured by
using a score function over the embedding vectors
($\mathbf{h},\mathbf{r},\mathbf{t}$). To evaluate the performances of KGE
models on link prediction, several benchmarks including FB15K, WN18 [6],
FB15K237 and WN18RR [7] are established by extracting subsets from large-scale
KGs, e.g., WordNet [8] and FreeBase [9].

The score functions of models play an important role in the performance of KGE
models. Numerous KGE models with a focus on score functions have been
proposed. Among them, several recent models, including ComplExN3 [10], RotatE
[11] and QuatE [14] take the advantage of hyper-complex representations and
high-dimensional embeddings to achieve the state-of-the-art results. The high
performances of RotatE, ComplExN3 and QuatE on FB15K are achieved by using
embeddings with the dimensions of 1000, 1000 and 2000. Due to the usage of
complex-valued vectors and quaternion vectors of ComplExN3 and QuatE, their
best performing settings result in 4000 adjustable parameters for each entity
and relation. On the other hand, for KGE models with higher embedding
dimensions, there is a risk of the redundancy of parameters leading to
unnecessary consumption on training time as well as memory space while the
generalisation capabilities of the learned models are not improved. For
example, the experimental results of ComplExN3 shows that the performances of
a ComplExN3 with 500-dimensional embeddings on FB15K237 and WN18RR are almost
same as a ComplExN3 with a embedding dimension of 2000.

Such observations show that the above mentioned state-of-the-art models take
advantages of high embedding dimensions and multiple-vector representation
resulting in a large embedding size $d$ which is equal to the total number of
adjustable parameters of each entity/relation embedding. In other words, these
models use single model with a multi-part high dimensional embeddings (the
total embedding size is $1\times d_{h}$). In contrast to those models, we use
the same model multiple ($k$) times in parallel trainings with low dimension
(the overall embedding size is $k\times d_{l}$). In order to have a fair
comparison, we enforce $k\times d_{l}=1\times d_{h}$ to guarantee that the
overall numbers of adjustable parameters of multiple low-dimensional models is
equal to the single high-dimensional model. Using multiple low dimensional
model instead of a single high dimensional model improves the expresivity of
various models in handling various patterns including symmetric, 1-n, n-1 and
n-n. The experimental results on three benchmarks show that the ensemble of
the same KGE model several times trained with low-dimensions results in a
better performances than training that model once with a high dimension,
regarding link prediction accuracy (higher expectations and lower standard
deviations) and training time.

##  II Related Work

KGE models can be roughly classified into two groups, distance-based models
and semantic matching models [5]. Here we review two distance-based KGE
models, i.e., TransE, RotatE and three semantic matching models i.e.,
DistMult, ComplEx and ComplExN3. Each KGE model defines a score function
$f(h,r,t)$ which takes embedding vectors of a triple
$(\mathbf{h},\mathbf{r},\mathbf{t})$ and returns a value showing the degree of
correctness of the triple.
TransE [6] computes the score of a triple $h,r,t$ by measuring the distance
between relation-specific translated head ($\mathbf{h}+\mathbf{r}$) and the
tail $\mathbf{t}$ as

$\displaystyle f(h,r,t)=-\|\mathbf{h}+\mathbf{r}-\mathbf{t}\|,$ (1)

to enforce $\mathbf{h}+\mathbf{r}\approx\mathbf{t}$ for each positive triple
($h,r,t$) in the vector space. The TransE model embeds entities/relation into
$d$ dimensional real space, i.e.,
$\mathbf{h},\mathbf{r},\mathbf{t}\in\mathbb{R}^{d}$.
RotatE [11] aims at mapping each element of the head embedding
($\mathbf{h}_{i}$) to the corresponding tail embedding $\mathbf{t}_{i}$ by
using relation-specific rotation $\mathbf{r}_{i}=e^{i\theta}.$ The score of
each triple $(h,r,t)$ is computed as

$f(h,r,t)=-\|\mathbf{h}\circ\mathbf{r}-\mathbf{t}\|,$ (2)

where $\circ$ is the element-wise multiplication and
$\mathbf{h},\mathbf{r},\mathbf{t}\in\mathbb{C}^{d}$. This enforces
$\mathbf{h}\circ\mathbf{r}\approx\mathbf{t}$ for each positive triple
($h,r,t$).
DistMult [15] is based on the Bilinear model [16] where each relation is
represented by a diagonal matrix rather than a full matrix. The formulation of
score function is

$f(h,r,t)=\mathbf{h}^{\top}\mathbf{diag(r)}\mathbf{t}=\sum_{i=0}^{d}\mathbf{h}_{i}\cdot\mathbf{r}_{i}\cdot\mathbf{t}_{i}.$
(3)

This score captures pairwise interactions between only the components of
$\mathbf{h}$ and $\mathbf{t}$ along the same dimension and thus can only deal
with symmetric relations.
CompEx [17] was proposed as an elegant way to solve the shortcoming of
DistMult in modeling asymmetric relation. Its main contribution is to embed
KGs in complex space. The score function is defined as

$\begin{split}f(h,r,t)=\mathrm{Re}(\mathbf{h}^{\top}\mathbf{diag(r)}\mathbf{\overline{t}})=\mathrm{Re}\left(\sum_{i=1}^{d}\mathbf{h}_{i}\mathbf{r}_{i}\bar{\mathbf{t}}_{i}\right),\end{split}$
(4)

where $\mathbf{r},\mathbf{h},\mathbf{t}\in\mathbb{C}^{d}$, $\mathbf{t}_{i}$
represents the complex conjugate of $\mathbf{t}$. By using this scoring
function, triples that have asymmetric relations can obtain different scores.
ComplExN3 [10] extends ComplEx with weighted nuclear 3-norm (N3
regularization) and uses a multi-class logistic loss function as optimization
objective to achieve the state-of-the-art results.

Krompass and Tresp [20] integer multiple different KGE models into one score
function and combines them during the training phase. Likewise, Muroemagi et
al. [22] combine different word embedding models using an iterative method.
However, we focus on stretching and squeezing the dimensions of the same
models which are trained separately and combined only for testing.

##  III Proposed Approach

Compared to TransE and DistMult, ComplExN3, RotatE and QuatE take advantages
of high-dimensional multi-part embeddings to achieve state-of-the-art
performances on link prediction. In these models, all parts of embeddings are
adjusted simultaneously. By contrast, in this part we propose a new approach
which combines multiple models of the same kind where each model contains low-
dimensional embeddings and is trained separately.

Let us have a model $\mathcal{M}$ (e.g. RotatE) with the embedding size $d$
where $d$ is equal to the total number of adjustable parameters of each
entity/relation embedding in a KGE model. Let $\mathcal{E}$ denote the set of
all entities and $\mathcal{R}$ the set of all relations present in a knowledge
graph. A triple is represented as $(h,r,t)$, with $h$, $t$ $\in\mathcal{E}$
denoting head and tail entities respectively and $r\in\mathcal{R}$ the
relation between them. We use
$\Omega=\\{(h,r,t)\\}\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{E}$
to denote the set of observed triples. We follow the steps below in our
approach:

  * (a)

We first generate $k$ times copies of an underlying model $\mathcal{M}$. The
$j$th copy of the model is denoted by $\mathcal{M}_{j},j=1,\ldots,k,$ and the
corresponding $d_{l}$ dimensional embeddings of $(h,r,t)$ are denoted by
$(\mathbf{h}_{j},\mathbf{r}_{j},\mathbf{t}_{j}).$ The vectors are randomly
initialized before training.

  * (b)

We then train each of the models $\mathcal{M}_{j},j=1,\ldots,k$ separately
with the same loss function. The training process can speed up by using
parallel computing.

  * (c)

Finally, the testing is performed by using the following score function

$f(h,r,t)=\frac{1}{k}\sum_{j=1}^{k}f_{\mathcal{M}}(\mathbf{h}_{j},\mathbf{r}_{j},\mathbf{t}_{j}),$
(5)

where $f_{\mathcal{M}}(\mathbf{h}_{j},\mathbf{r}_{j},\mathbf{t}_{j})$ is the
score of a triple $(h,r,t)$ computed by the $j$th copy of the model.

Figure 1 gives an example of representation learning with the ensemble of
multiple DistMult models, named as MDistMult. Firstly, the entity Berlin is
represented as a vector with a dimension of $k\times d_{l}$. Then the vector
is divided into $k$ separate vectors with dimensions of $d_{l}$. Each separate
vector is trained with a single DistMult model. Given a triple (Berlin,
Capital_of, Germany), its overall score is equal to the average of its scores
computed from the $k$ separate DistMult models.

Note that all models are trained on a same dataset with same hyperparamters
and the only two difference between the models is the random initialization of
the embedding vectors and the random sampling during the training process. To
verify the efficiency of our approach, we keep the overall embedding size
$d_{l}$ of multiple low-dimensional models same as the embedding size $d_{h}$
of the single high-dimensional model, i.e. $k\times d_{l}=d_{h}.$ We follow
the above steps to perform experiments on various state-of-the-art models,
including TransE, RotatE, DistMult, ComplEx and ComplExN3. We also test
DistMultN3, the extension of DistMult with the N3 regularizer. We will later
elaborate on the embedding initialization and the optimization objectives of
various models as well as the parallel training mechanism.

Figure 1: An example of multiple vector representation learning with MDistMult

###  III-A Initialization

In this work, combined multiple models of the same kind are trained with same
hyperparameters under the uniform experiment setting and the only two model
variations are from the random initialization of embeddings before the
training process and the random sampling during the training process.

Following the previous work on KGE, we use Xavier uniform initialization for
semantic matching models and Xavier norm initialization for distance-based
models. Xavier [26] initialization can make variances of each neuron layer
remain the same and thus bring a faster converge speed. Xavier uniform
initialization and Xavier norm initialization fill the input embedding with
values drawn from the uniform distribution $\mathcal{U}(-a,a)$ and the normal
distribution $\mathcal{N}(0,\sigma^{2})$ respectively, where

$\begin{split}a=\sqrt{\frac{6}{d_{in}+d_{out}}},\quad\sigma=\sqrt{\frac{2}{d_{in}+d_{out}}}.\end{split}$
(6)

For KGE model, $d_{in}$ is equal to the embedding size $d$ and $d_{out}=0$. We
follow the original experimental settings to uniformly initialize embeddings
for TransE, RotatE and use Xavier norm initialization for DistMult and
ComplEx. On the other hand, embeddings are initialized as sparse vectors for
ComplExN3 and DistMultN3. Since the random seed is not fixed in the
experiments, embeddings of different copies of the same model are initialized
as different vectors.

###  III-B Optimization

An appropriate loss function is quite important for model optimization. Most
of distance-based KGE models like TransE use a margin rank loss function as
optimization objective [6, 18, 19]. The original work introducing ComplEx
obtained the state-of-the-art results with a binary logistic loss function
[17]. RotatE adds a margin parameter into the binary logistic loss function
without the regularization term. This margin-based logistic loss function has
been proven to be helpful to enhance the performance of distance-based models
[11, 12, 13]. In this work, we utilize the binary logistic loss function to
train TransE, RotatE, DistMult and ComplEx. Given a training triple $(h,r,t)$,
the binary logisitic loss function is defined as follows,

$\displaystyle\mathcal{L}_{b}=$ $\displaystyle-\text{log}\
\sigma(\gamma+f_{\mathcal{M}}(h,r,t))-\sum_{i=1}^{\eta}p(h_{i}^{\prime},r,t_{i}^{\prime})\text{log}\
\sigma(-\gamma$ $\displaystyle-
f_{\mathcal{M}}(h_{i}^{\prime},r,t_{i}^{\prime}))+\lambda(||\mathbf{h}||_{2}^{2}+||\mathbf{r}||_{2}^{2}+||\mathbf{t}||_{2}^{2}).$
(7)

where $f(\cdot)$ denotes the specific score function of the KGE model
$\mathcal{M}$ as defined in the previous section, $\sigma(\cdot)$ denotes the
sigmoid function, $\gamma$ denotes the margin of distance-based model, $\eta$
is the number of negative samples per positive ones,
$(h_{i}^{\prime},r,t_{i}^{\prime})$ is the $i$th negative sample corresponding
to $(h,r,t)$ and $p(h_{i}^{\prime},r,t_{i}^{\prime})$ is the weight of the
negative sample which is computed from the following equation,

$p(h_{i}^{\prime},r,t_{i}^{\prime})=\frac{\text{exp}(f_{\mathcal{M}}(h_{i}^{\prime},r,t_{i}^{\prime}))}{\sum_{j=1}^{\eta}\text{exp}(f_{\mathcal{M}}(h_{j}^{\prime},r,t_{j}^{\prime}))}.$
(8)

Notice that the above loss function is exactly same as the binary logistic
loss function used in [17] when $\gamma=0$ and
$p(h_{i}^{\prime},r,t_{i}^{\prime})=1/\eta$. It is also equivalent to margin-
based logistic loss function defined in [11] when $\lambda=0$.

Different from previous work, ComplExN3 performs link prediction as a
multiclass classification task by using the full negative sampling and the
multi-class log-loss with N3 regularization instead of random negative
sampling and the binary logistic loss with L2 regularization [10, 21]. We
follow such setting for DistMultN3. The multiclass log-loss of a training
triple $(h,r,t)$ is defined as follows,

$\begin{split}&\mathcal{L}_{m}=\mathcal{L}_{m}^{1}+\mathcal{L}_{m}^{2}+\lambda(||\mathbf{h}||_{3}^{3}+||\mathbf{r}||_{3}^{3}+||\mathbf{t}||_{3}^{3}),\\\
&\mathcal{L}_{m}^{1}=-\text{log}(\frac{\text{exp}(f_{\mathcal{M}}(h,r,t))}{\sum_{h^{{}^{\prime}}\in\mathcal{E}}\text{exp}(f_{\mathcal{M}}(h^{{}^{\prime}},r,t))}),\\\
&\mathcal{L}_{m}^{2}=-\text{log}(\frac{\text{exp}(f_{\mathcal{M}}(h,r,t))}{\sum_{t^{{}^{\prime}}\in\mathcal{E}}\text{exp}(f_{\mathcal{M}}(h,r,t^{{}^{\prime}}))}).\end{split}$
(9)

###  III-C Parallel Training

Data parallelism and task parallelism are two common forms of parallel
computing. Data parallelism divides data equally among multiple processors and
instantaneously execute the same function over multiple data inputs across
multiple processors. In our case, the training process of each copy
$\mathcal{M}_{j}$ of the model $\mathcal{M}$ is taken as a separate task. For
each training task, since it is independent to each other, there is no risk of
being stuck with double buffering or waiting other tasks. Thus, we can utilize
task parallelism and data parallelism for training multiple KGE models at the
same time in multi-GPU environments.

Multiple models can also be trained parallelly in a single-GPU environment. A
single process may not utilize all the computation capacity and memory-
bandwidth available on the GPU. Nvidia Multi-Process Service (MPS) [23] allows
kernel and memcopy operations from different processes to overlap on the GPU,
achieving faster computation.

###  III-D Generalization Ability

The performance of a KGE model heavily relies on the ability of modeling
various graph patterns such as symmetric, 1-n, n-1 and n-n patterns. However,
not all patterns are encoded by as single KGE model. For example, TransE as a
baseline suffers from issue of modeling symmetric, 1-n, n-1 and n-n relations.
Here we show that our approach on training KGE models can help to cope with
expresivity issue of modeling patterns. We showcase the advantage of our
approach on TransE, which is one the baselines that has been reported to
suffer from various experisivity issues in modeling symmetric, 1-n, n-1 and
n-n relations [24].

Symmetric Pattern

Given a symmetric relation $r$ (e.g. SimilarTo), TransE cannot represent both
$\mathbf{h}+\mathbf{r}\approx\mathbf{t}$ and
$\mathbf{t}+\mathbf{r}\approx\mathbf{h}$ simultaneously while the relation
vector is non-zero. Therefore, given $\mathbf{r}\neq\mathbf{0}$, TransE can
express either

$\begin{split}&\mathbf{h}+\mathbf{r}\approx\mathbf{t},\mathbf{t}+\mathbf{r}\neq\mathbf{h},\quad\text{or}\\\
&\mathbf{h}+\mathbf{r}\neq\mathbf{t},\mathbf{t}+\mathbf{r}\approx\mathbf{h}.\end{split}$

Therefore, if the score of $(h,r,t)$ becomes zero, the score of $(t,r,h)$
becomes non-zero. For example, we have either case 1:
$f(h,r,t)=0,f(t,r,h)=\eta$ or case 2: $f(h,r,t)=\eta,f(t,r,h)=0$, which none
of them does not show being symmetric, even with using a very high embedding
dimension (e.g. 1000). That case 1 or case 2 happens depends on the several
random items used in the training (randomness in initialization, data
splitting and reshuffling etc). Therefore, in different run of a single
TransE, case 1 or 2 might be occurred. Therefore, a single model with any
dimension cannot properly represent symmetric pattern. Now let us train TransE
using our approach, denoted by MTransE. Assume we train two TransE models with
low dimension. Because of using two different runs, in which each one has its
own randomness, there is a possibility of having case 1 for the first slice of
TransE (i.e. TransE1) and case 2 for the second slice (TransE2). Therefore, we
have

$\begin{split}&\mathbf{h}_{1}+\mathbf{r}_{1}\approx\mathbf{t}_{1},\mathbf{t}_{1}+\mathbf{r}_{1}\neq\mathbf{h}_{1},\quad\text{and}\\\
&\mathbf{h}_{2}+\mathbf{r}_{2}\neq\mathbf{t}_{2},\mathbf{t}_{2}+\mathbf{r}_{2}\approx\mathbf{h}_{2}.\end{split}$

where $(\mathbf{h}_{1},\mathbf{r}_{1},\mathbf{t}_{1})$ are embeddings which
are associated to the first slice and
$(\mathbf{h}_{2},\mathbf{r}_{2},\mathbf{t}_{2})$ are used for the second
slice. The overall score of $(h,r,t)$ computed by MTransE becomes
$f(h,r,t)=0+\eta/2=\eta/2$ and for $(t,r,h)$, the score becomes
$f(t,r,h)=\eta/2+0=\eta/2$. Consequently, it is possible for MTransE to model
symmetric pattern.

n-1 Relation Pattern

In addition to symmetric, TransE suffers from encoding other patterns such as
1-n, n-1 and n-n relations. Here we focus on 1-n relation encoding in TransE
and our model.

For simplicity of explanation, let n=2. Assume $h^{1},h^{2}$ are two different
entities satisfying $(h^{1},r,t)$ and $a(h^{2},r,t)$ where $r$ is an n-1
relation. Since it is less likely that $\mathbf{h}^{1}=\mathbf{h}^{2}$.
Therefore, for the relation $r$ we have either

Figure 2: An example of MTransE modeling an n-1 relation

$\begin{split}&\mathbf{h}^{1}+\mathbf{r}=\mathbf{t},\mathbf{h}^{2}+\mathbf{r}\neq\mathbf{t},\quad\text{or}\\\
&\mathbf{h}^{1}+\mathbf{r}\neq\mathbf{t},\mathbf{h}^{2}+\mathbf{r}=\mathbf{t}.\end{split}$

Therefore, $(h^{1},r,t)$ and $(h^{2},r,t)$ get different scores while both are
positive triples (ranked differently).

Using MTransE, it is possible for the model to learn

$\begin{split}\mathbf{h}_{1}^{1}+\mathbf{r}_{1}=\mathbf{t}_{1},\mathbf{h}_{1}^{2}+\mathbf{r}_{1}\neq\mathbf{t}_{1}.\end{split}$

for the first slice and

$\begin{split}\mathbf{h}_{2}^{1}+\mathbf{r}_{2}\neq\mathbf{t}_{2},\mathbf{h}_{2}^{2}+\mathbf{r}_{2}=\mathbf{t}_{2}.\end{split}$

for the second slice. Therefore, we have $f(h^{1},r,t)=0+\eta_{1}/2$ and
$f(h^{2},r,t)=\eta_{2}/2+0$ for ($h^{1},r,t$), $(h^{2},r,t)$ respectively. As
shown in Figure 2, these two triples have the possibility of getting more
close scores and consequently are ranked more closely. The similar arguments
can be used for other models and patterns.

##  IV Experiments

####  IV-1 Dataset

We use FB15K [6], FB15K-237 and WN18RR [7] for evaluation. FB15K contains
relation triples from Freebase, a large tuple database with structured general
human knowledge. Another version of FB15K named as FB15K-237 has been created
to provide a more challenging KG after removing inverse relations. WN18RR is
extracted from an English lexical database, WordNet, with no inverse
relations. All datasets statistics are shown in Table 1.

TABLE I: Statistics of the datasets

.  Dataset $|\mathcal{E}|$ $|\mathcal{R}|$ #Train #Valid #Test FB15K 14951
1345 483142 50000 59071 FB15K237 14541 237 272115 17535 20466 WN18RR 40943 11
86835 3034 3134

####  IV-2 Evaluation Metric

We evaluate the performance of link prediction in the filtered setting: we
first rank a test triple $(h,r,t)$ against all other candidate triples not
appearing in the training, validation, or test set, where candidates are
generated by corrupting the subject: $(h,r,t^{\prime})$ to get the right rank
of $(h,r,t)$. Likewise, the left rank of $(h,r,t)$ is its rank against
candidate triples $(h^{\prime},r,t)$ where
$(h^{\prime},r,t)\notin\Sigma_{train}\cup\Sigma_{valid}\cup\Sigma_{test}$. We
use Mean Reciprocal Rank (MRR) and Hits@N for evaluation. The percentage of
testing triples which are ranked lower than N is considered as Hits@N. To
compute MRR, the following formula is used
$\text{MRR}=\frac{1}{2n}\sum_{i=1}^{n}\frac{1}{RR_{i}}+\frac{1}{LR_{i}}$ where
$n$ is the number of testing triples, $RR_{i}$ and $LR_{i}$ are the right rank
and the left rank of the $i$th test triple. To alleviate the noise from the
random initialization and the random sampling, in this paper we train and
evaluate each KGE model 10 times and compute the averages and the standard
deviations of its MRRs and Hits@Ns, no matter whether it is a single model or
a combination model. The averages of MRRs and Hits@Ns are denoted as
$\overline{\text{MRR}}$ and $\overline{\text{Hits@N}}$, the standard
deviations of MRRs and Hits@Ns are denoted as $\sigma_{\text{MRR}}$ and
$\sigma_{\text{Hits@N}}$.

####  IV-3 Experimental Setup

We evaluate our proposed approach by training TransE, RotatE, DistMult,
ComplEx, DistMultN3 and ComplExN3 in both single models with different
dimensions and multiple models with the same dimensions. In practice, an
overly small embedding size e.g., $d<100$ is not commonly used for KGE since a
KGE model with such a small embedding size is typically not expressive enough
to capture the semantics of entities and relations in a large-size KG, whereas
a KGE with a very large dimension size suffers from over-fitting and excessive
consumptions on memory size and training time. Thus, we set the embedding size
to $d=\\{200,400,600,800,1000,1200\\}.$ Another noteworthy point is that we
define the embedding size $d$ as the total number of adjustable parameters in
each embedding. For a complex-valued embedding model, e.g., ComplEx, the
embedding size is as twice as the embedding dimension since each dimension has
two elements of the real part and the imaginary part. To train TransE, RotatE,
DistMult and ComplEx, we use an Adam optimizer with a learning rate $lr$ of
0.0003 and adopt the random negative sampling. The number of mini batches is
fixed as 100, the ratio of negatives over positive training samples $\eta$ is
tuned among {$1,3,5,8,10$}, the margin $\gamma$ of a distance-based model is
tuned among $\\{1,3,5,8,10,15,20,25,30\\}$ and the regularization coefficient
$\lambda$ of a semantic matching model is searched in
$\\{0.1,0.03,0.01,0.003,0.001\\}$. For DistMultN3 and ComplExN3, we follow the
experimental setting in [10] to use an Adagrad optimizer with a learning rate
$lr$ of 0.1 and tune the batch size $b$ in {$100,1000$}, regularization
coefficient $\lambda$ in $\\{0.1,0.05,0.01,0.005,0.001\\}$. We use the early-
stop setting on validation set and set the maximum epoch to 5000. A
combination model of multiple models of a same kind is named with an initial
M, e.g., an MTransE model is the ensemble of multiple TransE models. The
implementation has been done by using Pytorch on a single GPU device.

##  V Results and Discussion

Figure 3: Link prediction results of the tested models with the same embedding
size $d=1200$ and different numbers $k$ of the combined models on FB15K

###  V-A Link Prediction Results

We first study the effect of $k$ on the performance of the ensemble KGE models
(e.g., MTransE, MRotatE, MDistMult, MComplEx, MDistMultN3 and MComplExN3) by
fixing the overall embedding size $d=1200$ and tuning $k\in\\{1,2,\dots,6\\}$.
As shown in Figure 3, when the embedding sizes are fixed as 1200, the number
of combined KGE models of the same kind $k$ higher, the performance on FB15K
of the combination KGE model better regarding the averages and the standard
deviations of MRR and Hits@3. This observation supports the intuition that the
ensemble of multiple models can alleviate the noise from the random
initialization of single models.

Figure 4: $\overline{\text{MRR}}$ for link prediction of all tested models with different overall embedding sizes $d$ on KGE benchmarks Figure 5: $\overline{\text{Hits@3}}$ for link prediction of the tested models with different overall embedding sizes $d$ on KGE benchmarks TABLE II: Link prediction results on FB15K and FB15K-237. | FB15K | FB15K-237
---|---|---
| $\overline{\text{MRR}}$ | $\overline{\text{Hits@1}}$ | $\overline{\text{Hits@3}}$ | $\overline{\text{Hits@10}}$ | $\overline{\text{MRR}}$ | $\overline{\text{Hits@1}}$ | $\overline{\text{Hits@3}}$ | $\overline{\text{Hits@10}}$
TransE ($d=1200$) | 0.704 | 0.604 | 0.781 | 0.862 | 0.277 | 0.186 | 0.303 | 0.464
MTransE ($d=6*200$) | 0.732 | 0.640 | 0.802 | 0.876 | 0.298 | 0.202 | 0.329 | 0.491
DitMult ($d=1200$) | 0.688 | 0.573 | 0.781 | 0.855 | 0.227 | 0.142 | 0.249 | 0.390
MDitMult ($d=6*200$) | 0.718 | 0.603 | 0.815 | 0.883 | 0.237 | 0.160 | 0.260 | 0.399
ComplEx ($d=1200$) | 0.696 | 0.580 | 0.791 | 0.862 | 0.226 | 0.139 | 0.249 | 0.398
MComplEx ($d=6*200$) | 0.710 | 0.590 | 0.810 | 0.886 | 0.240 | 0.162 | 0.264 | 0.400
RotatE ($d=1200$) | 0.727 | 0.630 | 0.802 | 0.868 | 0.290 | 0.197 | 0.319 | 0.478
MRotatE ($d=6*200$) | 0.753 | 0.656 | 0.832 | 0.891 | 0.307 | 0.213 | 0.338 | 0.496
DitMultN3 ($d=1200$) | 0.836 | 0.796 | 0.865 | 0.909 | 0.355 | 0.260 | 0.390 | 0.547
MDitMultN3 ($d=6*200$) | 0.848 | 0.813 | 0.869 | 0.910 | 0.357 | 0.263 | 0.392 | 0.548
ComplExN3 ($d=1200$) | 0.843 | 0.802 | 0.871 | 0.910 | 0.360 | 0.265 | 0.395 | 0.549
MComplExN3 ($d=6*200$) | 0.859 | 0.829 | 0.877 | 0.911 | 0.364 | 0.268 | 0.400 | 0.555

We further compare the link prediction performances of single high-dimensional
KGE models (e.g., TransE, RotatE, DistMult, ComplEx, DistMultN3 and ComplExN3)
and the simple ensembles of multiple low-dimensional KGE models of the same
kinds (e.g., MTransE, MRotatE, MDistMult, MComplEx, MDistMultN3 and
MComplExN3) with the same dimension sizes. The embedding size of each low-
dimensional KGE models are fixed as 200 and we change the embedding size $d$
of an ensemble model, e.g., MTransE by tuning the number of the combined low-
dimensional models $k$, i.e., $d=200\times k,k=1,2,\dots,6$.

Figure 6: Training time per epoch of (M)ComplEx and (M)RotatE with different
embedding sizes $d$

Figure 4 and Figure 5 show the link prediction results of the single high-
dimensional models and the multiple low-dimensional models regarding
$\overline{\text{MRR}}$ and $\overline{\text{Hits@3}}$. Averagely, the
ensembles of multiple low-dimensional models outperform the corresponding
high-dimensional single models with the same overall embedding sizes. We
notice that the performance of a single KGE model might decrease with the
embedding size increasing, e.g., RotatE ($d=1000$) and RotatE ($d=1200$) have
lower $\overline{\text{MRR}}$s and $\overline{\text{Hits@3}}$s than RotatE
($d=800$) on FB15K. This observation demonstrates that using embeddings with
an overly large embedding size leads to a risk of overfitting, especially for
distance-based KGE models. By contrast, the ensemble of $k+1$ KGE models of a
same kind always outperforms the ensemble of $k$ KGE models of the same kind
since the new added model improves the generalization ability of the ensemble
model.

To clearly compare the ensemble KGE models and the single KGE models which
have the same overall embedding sizes and scoring functions, Table II lists
the link prediction results of all target KGE models with the same overall
embedding size of $d=1200$ on FB15K and FB15K237 regarding
$\overline{\text{MRR}}$, $\overline{\text{Hits@1}}$,
$\overline{\text{Hits@3}}$ and $\overline{\text{Hits@10}}$. For any kind of
KGE approach, its high-dimensional model with $d=1200$ underperforms the
ensemble of its low-dimensional models with the same overall embedding size
across all metrics. For instance, MComplExN3 with $d=1200$ improves 1.6 points
of $\overline{\text{MRR}}$ and 2.7 points of $\overline{\text{Hits@1}}$
compared to ComplExN3 with $d=1200$.

###  V-B Quality Analysis

Table III reports the $\overline{\text{MRR}}$s of TransE ($d=200\times 1$),
TransE ($d=1200\times 1$) and MTransE ($d=200\times 6$) on link prediction
involving different relation patterns in FB15K. Following the setting in [24],
we separate relations into 4 categories: 1-1, 1-n, n-1 and n-n. Within the
1345 relations in FB15K, 24% are 1-1, 23% are 1-n, 29% are n-1, and 24% are
n-n. We also employ AMIE+ [25] to extract 24 symmetric relations
(r(x,y)$\Rightarrow$r(y,x)) from FB15K with a confidence threshold of 0.8. A
few typical symmetric relations include person/sibling and person/spouse. As
shown in Table III, TransE ($d=1200\times 1$) have the close performance to
MTransE ($d=200\times 6$) on 1-1 relations, meanwhile MTransE significantly
outperforms both TransE ($d=1200\times 1$) and TransE ($d=200\times 1$) on
other complex relation patterns. MTransE can enhance the expressiveness and
the generalization ability of TransE by comprehensively considering the link
prediction results of multiple TransE models to alleviate the negative effect
of TransE’s limitation on modeling 1-n, n-1, n-n and symmetric relations. More
concretely, Table IV gives an example of how MTransE improves the performance
of TransE models on modeling tv_program/language, an n-1 relation. Given four
test triples involving the same relation tv_program/language and the same tail
entity English with different head entities, the first TransE model models
triples (”Parks and Reactions”, tv_program/language, English) well while the
second TransE model predicts (”Angel”, tv_program/language, English)
correctly. By combining these two models, the ensemble model MTransE can
predict both triples precisely. Meanwhile, the ranks of other two head
entities which are underrated by both TransE models are improved by the
MTransE model.

TABLE III: $\overline{\text{MRR}}$ of (M)TransE models with different
embedding size $d$ on FB15K regarding different relation patterns

.  TransE TransE MTransE Relation ($d$=200$\times$1) ($d$=1200$\times$1)
($d$=200$\times$6) 1-1 0.642 0.663($\uparrow$0.021) 0.660($\uparrow$0.018) 1-n
0.739 0.748($\uparrow$0.009) 0.780($\uparrow$0.041) n-1 0.639
0.650($\uparrow$0.011) 0.678($\uparrow$0.039) n-n 0.706 0.709($\uparrow$0.003)
0.739($\uparrow$0.033) symmetric 0.358 0.360($\uparrow$0.002)
0.411($\uparrow$0.053)

TABLE IV: The filtered ranks of head entities $h$ regarding the query (?,
tv_program/language, English) obtained from TransE and MTransE models

.  TransE1 TransE2 MTransE Head Entity ($h$) ($d$=200$\times$1)
($d$=200$\times$1) ($d$=200$\times$2) ”Parks and Recreation” 1 5 1 ”Angel” 4 1
1 ”Jesus of Nazareth” 16 8 6 ”Nurse Jackie” 5 6 3

###  V-C Training Time

By using MPS, we can efficiently train multiple low-dimensional KGE models on
a single GPU simultaneously. We conduct all experiments on a TITAN X (Pascal)
GPU. As shown in Figure 6, the time cost per epoch of training multiple low-
dimensional KGE models, e.g., MRotatE ($d=200\times k$) and MComplEx
($d=200\times k$), is less than training a single high-dimensional KGE model,
e.g., ComplEx and RotatE, with the same overall embedding size $d$.

##  VI Conclusion

In this work, we empirically study the effect of the embedding size on the
performance of several common KGE models and propose a performance boosting
training strategy for KGE models without enlarging the overall embedding sizes
of models. Concretely, we first divide a high-dimensional embedding into
several low-dimensional embedding and input them into the respective KGE
models of the same kind which are separately trained. All models are combined
only at the query time. Given a triple ($h,r,t$), its final overall score is
equal to the average of its scores computed from multiple models. We show that
our approach can improve the generalization ability of KGE models on modeling
various complex relation patterns. And the training processes of multiple KGE
models can be completed efficiently by using parallel training. Experimental
results demonstrate that the ensembles of multiple low-dimensional KGE models
of the same kind outperform the corresponding single high-dimensional KGE
models with the same embedding size.

## Acknowledgment

This work is supported by the EC Horizon 2020 grant LAMBDA (GA no. 809965),
the CLEOPATRA project (GA no. 812997) and the China Scholarship Council (CSC).

## References

  * [1] G. A. Miller. “WordNet: a lexical database for English,” Communications of the ACM 38, 1995, pp. 39-41.
  * [2] K. Bollacker, C. Evans, P. Paritosh, T. Sturge and J. Taylor. “Freebase: a collaboratively created graph database for structuring human knowledge,” In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, 2008, pp. 1247-1250.
  * [3] F. M. Suchanek, G. Kasneci and G. Weikum, “Yago: a core of semantic knowledge,” In Proceedings of the 16th international conference on World Wide Web, 2007, pp. 697-706.
  * [4] S. Auer, C. Bizer, G. Kobilarov, J. Lehmann, R. Cyganiak, Z. Ives, “Dbpedia: A nucleus for a web of open data,” In The semantic web, 2007, pp. 722-735.
  * [5] Q. Wang, Z. Mao, B. Wang, L. Guo. “Knowledge graph embedding: A survey of approaches and applications,” IEEE Transactions on Knowledge and Data Engineering, 2017, no. 12, pp. 2724-2743.
  * [6] A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston and O. Yakhnenko, “Translating embeddings for modeling multi-relational data,” Advances in neural information processing systems, 2013, pp. 2787-2795.
  * [7] T. Dettmers, P. Minervini, P. Stenetorp and S. Riedel, “Convolutional 2d knowledge graph embeddings,” In Proceedings of the AAAI Conference on Artificial Intelligence, 2018, vol. 32, no. 1.
  * [8] G. A. Miller, “WordNet: a lexical database for English,” Communications of the ACM, 1995, 38(11), pp. 39-41.
  * [9] K. Bollacker, C. Evans, P. Paritosh, T. Sturge and J. Taylor, “Freebase: a collaboratively created graph database for structuring human knowledge,” In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, 2008, pp. 1247-1250.
  * [10] T. Lacroix, N. Usunier, G. Obozinski, “Canonical tensor decomposition for knowledge base completion,” In International Conference on Machine Learning, 2018.
  * [11] Z. Sun, Z. Deng, J. Nie, and J. Tang. “Rotate: Knowledge graph embedding by relational rotation in590complex space,” In International Conference on Learning Representations, 2019.
  * [12] C. Xu, M. Nayyeri, F. Alkhoury, H. Yazdi, J. Lehmann, “Temporal Knowledge Graph Completion Based on Time Series Gaussian Embedding,” In International Semantic Web Conference, 2020, pp. 654-671.
  * [13] C. Xu, M. Nayyeri, F. Alkhoury, H. Yazdi, J. Lehmann, ”TeRo: A Time-aware Knowledge Graph Embedding via Temporal Rotation.” arXiv: 2010.01029, 2020.
  * [14] S. Zhang, Y. Tay, L. Yao and Q. Liu, “Quaternion Knowledge Graph Embedding,” In Advances in neural information processing systems, 2019.
  * [15] B. Yang, W. T. Yih, X. He, J. Gao and L. Deng, “Embedding entities and relations for learning and inference in knowledge bases,” In International Conference on Learning Representations, 2014.
  * [16] M. Nickel, V. Tresp, H. P. Kriegel, “A three-way model for collective learning on multi-relational data,” In International Conference on Machine Learning (ICML), 2011, vol. 11, pp. 809-816.
  * [17] T. Trouillon, J. Welbl, S. Riedel, E. Gaussier and G. Bouchard, “Complex embeddings for simple link prediction,” In International Conference on Machine Learning (ICML), 2016.
  * [18] M. Nayyeri, C. Xu, S. Vahdati, N. Vassilyeva, E. Sallinger, H. Yazdi, J. Lehmann, ”Fantastic Knowledge Graph Embeddings and How to Find the Right Space for Them.” International Semantic Web Conference. Springer, Cham, 2020, pp. 438-455.
  * [19] M. Nayyeri, C. Xu, S. Vahdati, E. Sallinger, H. Yazdi, J. Lehmann, ”On the knowledge graph completion using translation based embedding: the loss is as important as the score.” arXiv preprint arXiv: 1909.00519 , 2019.
  * [20] D. Krompaß, V. Tresp, “Ensemble solutions for link prediction in knowledge graph,” In Proceedings of the 2nd Workshop on Linked Data for Knowledge Discovery, 1-10.
  * [21] C. Xu, M. Nayyeri, Y. Chen, J. Lehmann, ”Knowledge graph embeddings in geometric algebras.” arXiv preprint arXiv: 2010.00989, 2020.
  * [22] A. Muromägi, K. Sirts, S. Laur, “Linear ensembles of word embedding models,” arXiv preprint arXiv: 1704.01419, 2017.
  * [23] P. Sah, “Improving gpu utilization with multi-process579service (MPS),” In GPU Technology Conference, 2015, vol. 5584.
  * [24] Z. Wang, J. Zhang, J. Feng and Z. Chen, “Know1edge Graph Embedding by Translating on Hyperplanes,” In Proceedings of the AAAI Conference on Artificial Intelligence, 2014, pp. 1112–1119.
  * [25] L. Galárraga, C. Teflioudi, K. Hose, F. M. Suchanek, “Fast rule mining in ontological knowledge bases with AMIE+,” The VLDB Journal, 2015, no. 6, pp. 707-730.
  * [26] X. Glorot, Y. Bengio. “Understanding the difficulty of training deep feedforward neural networks,” In Proceedings of the thirteenth international conference on artificial intelligence and statistics, 2010, pp. 249-256.


# CloudSec: An Extensible Automated Reasoning Framework for Cloud Security
Policies ††thanks: This material is based upon work supported by the National
Science Foundation Office of Advanced CyberInfrastructure, Collaborative
Proposal: Frameworks: Project Tapis: Next Generation Software for Distributed
Research(Award #1931439)

Joe Stubbs  Texas Advanced Computing Center
University of Texas at Austin
Austin, TX, USA
<EMAIL_ADDRESS>Smruti Padhy  Texas Advanced Computing Center
University of Texas at Austin
Austin, TX, USA
<EMAIL_ADDRESS>Richard Cardone  Steven Black *The first two authors
contributed equally to this work. Texas Advanced Computing Center
University of Texas at Austin
Austin, TX, USA
<EMAIL_ADDRESS>Texas Advanced Computing Center
University of Texas at Austin
Austin, TX, USA
<EMAIL_ADDRESS>
###### Abstract

Users increasingly create, manage and share digital resources, including
sensitive data, via cloud platforms and APIs. Platforms encode the rules
governing access to these resources, referred to as security policies, using
different systems and semantics. As the number of resources and rules grows,
the challenge of reasoning about them collectively increases. Formal methods
tools, such as Satisfiability Modulo Theories (SMT) libraries, can be used to
automate the analysis of security policies, but several challenges, including
the highly specialized, technical nature of the libraries as well as their
variable performance, prevent their broad adoption in cloud systems. In this
paper, we present CloudSec, an extensible framework for reasoning about cloud
security policies using SMT. CloudSec provides a high-level API that can be
used to encode different types of cloud security policies without knowledge of
SMT. Further, it is trivial for applications written with CloudSec to utilize
and switch between different SMT libraries such as Z3 and CVC5. We demonstrate
the use of CloudSec to analyze security policies in Tapis, a cloud-based API
for distributed computational research used by tens of thousands of
researchers.

###### Index Terms:

Distributed computing, authentication, authorization, HPC, microservices,
middleware

##  I Introduction

Through the use of cloud-based applications and services, users create
valuable digital assets that must be secured. Each cloud platform makes use of
a system for managing and enforcing the rules regarding which users have
access to which digital assets, and there is little standardization across the
vast number of such systems. For example, each of the major cloud computing
providers have their own, independent systems for access management: Amazon
Web Services makes use of AWS IAM [1], Google Cloud Platform uses Google IAM
[2], and Microsoft Azure provides Azure Role Based Access Control (RBAC) [3].
Kubernetes, the popular container orchestration system, has its own RBAC
policy system [4]. There are also many popular open source projects providing
these capabilities, including Casbin [5], KeyCloak [6], Open Policy Agent [7],
etc.

As systems evolve over time and as the number of digital assets and rules,
referred to as security policies, grows, ensuring policies are correctly
written and match what is being enforced becomes more difficult. In
particular, when the relationship between a user and a system changes – for
example, because the user is taking on new responsibilities as part of their
job or changing jobs altogether – entire sets of security rules often must be
updated, and it can be very difficult to be sure the updated set enforces the
correct access controls.

Software based on formal methods such as Satisfiability Modulo Theories (SMT)
( [8],[9]) libraries provide techniques for automatically reasoning about
entire collections of policies, and to prove or find counter-examples to
mathematically precise statements regarding the policies. For example, in a
cloud system that provides access to different types of files stored across
various backends, SMT can be used to determine if a set of security policies
satisfies “rules” such as: developers have access to code repositories but not
other files, data scientists have access to datasets for model training but
not code repositories, and project managers have access to testing results but
not training data or code. However, the broad adoption of SMT in cloud systems
faces the following challenges: 1) the use of these tools requires a
sophisticated understanding of the underlying SMT; 2) a significant effort
must be made to encode a particular security policy’s semantics into an SMT
library; and 3) performance on different security policy sets varies across
different SMT libraries and even different versions of the same library.

To address these challenges, we built CloudSec [10], an extensible automated
reasoning framework for cloud security policies that do not require any SMT
knowledge to use or extend to new cloud policy systems. CloudSec defines a set
of core Components – basic data types for defining the semantics of a security
policy – as well as the PolicyType and Policy abstract classes. These are
linked to SMT solvers through CloudSec’s library of backends, which implement
encodings of the generic Components data types as well as proof methods based
on the functionality provided by the solver. The initial release of CloudSec
[10] includes support for the Z3 ([11], [12]) and CVC5 ([13], [14]) libraries
as backends. Using CloudSec’s building blocks, the policy types for a new
system can be defined in just a few lines of Python code without any
understanding of SMT.

As open-source software, CloudSec can be used to analyze the performance of
different backend solvers transparently. In this paper, we present CloudSec
API demonstrating the use of Z3 and CVC5 solvers as backends. Furthermore, we
utilize CloudSec to analyze security policies within the Tapis API platform
[15], a modern cloud platform enabling automated, secure, collaborative
research computing. Used by thousands of researchers to automate data
management and analysis tasks, Tapis software components run across several
institutions and support dozens of independent projects, or “tenants” and
utilizes a robust permissions model that includes hierarchical roles,
permission “types” with schemas for many services, and a multi-tenant
authentication system. This multi-site, multi-tenant architecture compounds
the challenge of ensuring that resources are not accidentally exposed to
unauthorized parties. Using CloudSec we automatically establish or find
counter-examples to policy requirements across entire sets of thousands of
Tapis permissions.

In summary, the main contributions of this paper are:

  * 1.

Design and implementation of CloudSec, an extensible Python framework for
leveraging SMT for security policy analysis with a user-friendly interface.

  * 3.

Description of CloudSec usage in Tapis, a real-world cloud platform used by
thousands of researchers.

The rest of the paper is organized as follows: In Section 2, we provide
background material on Tapis; in Section 3, we describe the CloudSec design,
its use in Tapis, and give examples of policy types and encodings; in Section
4, we briefly discuss the initial performance results of CloudSec; in Section
5 we discuss the related work; and we conclude in Section 6 and outline some
areas for future work.

##  II Background

In this section, we provide background information on topics used throughout
the rest of this paper.

###  II-A Tapis

Tapis [15] is a web-friendly, application programming interface (API) for
research computing, allowing users to automate their interactions with
advanced storage and computing resources in cloud and HPC datacenters. Primary
Tapis features include a full-featured data management service, with
synchronous endpoints for data ingest and retrieval as well as a reliable
asynchronous data transfer facility; workload scheduling and code execution; a
highly-scalable document store and metadata API; and support for streaming
IoT/sensor data. Tapis supports reproducibility by recording a detailed data
provenance and computation history of actions taken in the platform.
Additionally, Tapis enables collaboration via a fine-grained permissions
model, allowing data, metadata and computations to be kept private, shared
with specific individuals or disseminated to entire research communities.
Tapis has been used by thousands of researchers across projects funded by a
number of government agencies, including CDC, DARPA, NASA, NIH, and NSF.

###  II-B Tapis Security Policies

Tapis is organized as a set of 14 independent HTTP web services (sometimes
called microservices) that coordinate together to accomplish larger tasks. The
Tapis Security Kernel (SK) manages all authorization data – information
specifying which users have access to which Tapis objects and at what access
level. SK stores this authorization data as permission objects and provides
HTTP endpoints for creating, retrieving, and modifying permissions.

##  III Approach

As mentioned in the Introduction, CloudSec provides a toolkit in the form of a
Python library for utilizing SMT solvers to analyze security policies in real-
world systems such as Tapis. The primary goal of CloudSec is to reduce the
expertise needed to apply SMT technology to the study of security policies.

Figure 1: CloudSec Overview and Usage Model

###  III-A Design Challenge

The primary design challenge faced by CloudSec was to provide abstractions
with sufficient expressive power to support a large number of policy types
while not requiring knowledge of SMT. CloudSec achieves this goal by
decoupling the interface used for policy encoding from that used for policy
analysis.

###  III-B CloudSec - Extensible Framework Design

The primary components of the CloudSec framework include (i) the core module,
with basic data types that can be used to build encodings of real-world
security policy systems; (ii) the backends library, which provides
implementations of encodings of the types provided in the core module as well
as proof methods for analyzing sets of policies via various solvers, such as
Z3 and cvc5; (iii) the cloud module, which utilizes the types provided in core
to define ready-to-use policy types for real systems; and (iv) the connectors
library, which provides functions for converting security rules in source
systems to CloudSec policies.

Central to the design of CloudSec are the concepts of Component, PolicyType,
and Policy, provided by the core module. Each Component type contains a data
type, such as a String, Enumeration, IP Address or Tuple, the set of allowable
values for the data type, and a matching strategy, which defines a “match”
relation on two values from the set of allowable values for the data type.
Examples of currently supported matching strategies include exact matching and
wildcard matching. PolicyTypes build on the notion of Components, with each
PolicyType defining a list of Components that it is comprised of. Finally, a
Policy object represents a specific value for a given PolicyType.

Using these primary notions, one can create PolicyTypes comprised of
Components for real-world systems in just a few lines of Python without
requiring any knowledge of SMT. The cloud module provides examples of
PolicyType objects, including a tapis_files_policy_type, used to represent
policies related to file objects in Tapis, and an http_api_policy_type, which
can be used to model policies in an arbitrary HTTP API. Moreover, by
decoupling the definitions of Components and PolicyTypes from their
implementations in different backend solvers, CloudSec provides a highly-
extensible system in which support for additional solvers can be added
independently of defining policy types for new systems.

###  III-C An Example Policy Type and Policy Definition

As a first example, we describe the http_api_policy_type, available in the
CloudSec toolkit. We created this policy type to illustrate what can be
achieved with CloudSec. The policy type represents policies governing access
to resources defined in a multi-tenant, microservice API platform. The policy
type is comprised of three components: principal, resource, and action. A
principal is a Tuple component type with two fields, tenant and username,
representing a unique user identity in the platform to whom access to some
resource is being allowed or denied by the policy. A tenant is a StringEnum
component with enumerated values representing all possible tenants. We chose a
StringEnum to model the tenant under the assumption that the number of tenants
would be relatively small. On the other hand, the username field is modeled
with a String component type defined over an alphanumeric set and maximum
length.

Similarly, a resource is modeled using a Tuple component type with three
fields, tenant, service, and path, that collectively distinguish a specific
HTTP endpoint (i.e., HTTP resource) within a service to which access is being
allowed or denied in some tenant. A service is a StringEnum component with
enumerated values representing the names of the APIs in the platform. The path
is a String component defined over a path character set with a maximum length.
The path represents the URL path corresponding to the resource. Finally, the
action is a StringEnum that denotes the HTTP method being authorized or not
authorized, such as {“GET”,“POST”,“PUT”,“DELETE”}. An example policy
definition of http_api_policy_type is shown below:

⬇

p = Policy(policy_type=http_api_policy_type,

principal=(“a2cps”,“jdoe”),

resource=(“a2cps”,“files”,

“/ls6/home/jdoe”),action=“GET”,

decision=“allow”)”

Note that all policy types have a special decision field which is a StringEnum
with values “allow” and “deny”.

###  III-D Tapis Policy Types

The CloudSec toolkit includes policy types representing permissions objects in
the Tapis API platform. For example, we provide the tapis_files_policy_type
for dealing with Tapis permissions related to file objects. The
tapis_file_perm component is a Tuple type representing the Tapis files “perm
spec” (see [16]) and includes fields for the tenant, system id, permission
level, and file path. Because of the simple and flexible CloudSec core API,
the entirety of the Tapis policy type implementations constitutes less than 20
lines of Python code.

###  III-E Translating a Policy Set to SMT Formula

A policy set is defined as a set of policies, i.e.,
$PS=\\{P_{1},P_{2},\cdot\cdot\cdot,P_{i},\cdot\cdot\cdot,P_{n-1},P_{n}\\}$
where $1\leq i\leq n$. Each policy,
$P_{i}=(c_{1},c_{2},\cdot\cdot\cdot,c_{j},\cdot\cdot\cdot,c_{m-1},c_{m},Decision)$
where $1\leq j\leq m$. $c_{j}$ denotes the value for Component $C_{j}$ of
Policy $P_{i}$. Note that a policy type determines the number and type of
Components in a policy. $Decision$ is a value from the set
$\\{``allow",``deny"\\}$ to denote if a policy allows or denies access. A
policy is translated to an SMT formula as:

$\mathcal{P}=\bigwedge_{j=1}^{m}\left(\bigvee_{c\in C_{j}(P)}C_{j}=c\right)$

$C_{j}(P)$ denotes set of values defined for Component $C_{j}$ in a policy
$P$. If $C_{j}(P)$ is a Tuple component type with $k$ components , let say,
$(t_{1},t_{2},..,t_{k})$, then it is further encoded as
$\bigwedge_{l=1}^{k}\left(t_{k}=v\right)$ where component $t_{k}$ takes one of
the component allowed values, $v$.

A policy set can be SMT encoded as:

$\mathcal{PS}=\left(\bigvee_{AllowSet}\mathcal{P}\right)\bigwedge\neg\left(\bigvee_{DenySet}\mathcal{P}\right)$

Where $AllowSet=\\{\forall P\in PS:P.Decision=``allow"\\}$ and
$DenySet=\\{\forall P\in PS:P.Decision=``deny"\\}$

###  III-F Connectors and Converting SK Policies to Cloudsec

using CloudSec to analyze security rules from a real-world system requires one
to generate CloudSec policy objects (of the appropriate type) from
authorization data residing in the external system. A CloudSec connector can
be written for the external system to simplify this effort. The CloudSec
toolkit currently includes a connector for Tapis files permissions, allowing
CloudSec tapis_files_policy_type policies to be generated from Tapis
permissions data with a single function call.

Using CloudSec, we developed a program that generates Tapis files policy
objects from all Tapis files permissions in the SK for a configurable set of
users. The program then uses CloudSec solver backends to prove that the source
policies conform to certain rules or find counter examples. For instance,
using our program, we analyzed policies for users within a certain project
built with Tapis, generating over 3,000 CloudSec policies. We then were able
to prove that for this project, no users except for the users in the admin-
scientist role had read/write access to files in a protected data directory on
a specific Tapis system. Similarly, we prove that public access to generated
result files is restricted to files with a .png extension.

Establishing these kinds of results harnesses the full power of CloudSec –
while the Tapis SK is highly efficient at answering the question, “does a
given user have access to a specific resource?”, it cannot reason about an
entire set of permissions at once. Furthermore, our program must use both Z3
and cvc5 to find proofs like the ones above, as some proofs could not be found
by one solver or the other.

We did an initial performance evaluation of the CloudSec toolkit 1) to
establish that the CloudSec software was a viable approach (i.e., can be done
on commodity hardware in a reasonable amount of time) to analyze policies of
the sizes that show up in real systems such as Tapis (i.e., on the order of a
few thousand policies) (Section III-F); and 2) to show that CloudSec could be
used as a framework for comparing different SMT backends for specific analyses
[10]. We also observed that there are scenarios for which either Z3 or CVC5 or
both, along with their different versions exhibit performance cliffs.

##  IV Performance

We did a performance evaluation of the CloudSec toolkit 1) to establish that
the CloudSec software was a viable approach (i.e., can be done on commodity
hardware in a reasonable amount of time) to analyze policies of the sizes that
show up in real systems such as Tapis (i.e., on the order of a few thousand
policies) (Section III-F); and 2) to show that CloudSec could be used as a
framework for comparing different SMT backends for specific analyses [10]. We
also observed that there are scenarios for which either Z3 or CVC5 or both,
along with their different versions exhibit performance cliffs. We provide the
details of the performance evaluation in subsequent subsections.

We measured the performance to check trivial implications for two policy sets
as the number of policies grows. We defined different components (String and
StringEnum) and policy types using those components to create policy sets.
Each policy set consists of policies of the same policy type. We repeated the
test for both Z3 and cvc5 backends. We ran the tests on a machine with the
following configuration: 32 CPUs, Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz,
128 GB RAM.

###  IV-A StringEnum Scalability

We defined a policy type containing a StringEnum with a variable number, $N$,
allowable values and with wildcard matching. For example, with $N=5$, the
policy type’s StringEnum will have allowable values { ‘0’, ‘1’,‘2’,‘3’,‘4’}.
We created two policy sets, $P$ and $Q$. $P$ contained a policy $P_{i}$ for
every allowable value, i.e., $P=\cup_{i=0}^{N-1}\\{(P_{i},``allow")\\}$ where
$P_{i}=i$. $Q$ contained a single wildcard policy, $Q=\\{(*,``allow")\\}$. We
varied the number of unique elements, $N$, in the range $10\leq N\leq 4000$.
We measured the time to perform: 1) data load, 2) SMT encoding, 3) $P\implies
Q$ and 4) $Q\implies P$ for Z3 as well as for cvc5. In Figure 2 a, we observed
that when using the Z3 backend, the SMT encoding, $P\implies Q$ and $Q\implies
P$ took similar amounts of time, while the data load took significantly less
time. When we used cvc5, SMT encoding took the most of the computation time
while the data load time was more than the implication prove time. For this
performance test, cvc5 was roughly 90% faster than Z3 in total time.

(a)

(b)

Figure 2: Dynamic StringEnum Policy type Scalability

###  IV-B String with wildcard Scalability

We defined a policy type with a single String component with wildcard
matching. The string component was defined over a character set that included
alphanumeric characters, ‘/’, and the wildcard character ‘*’. The maximum
length of the string was 100. We created two policy sets, $P$ and $Q$, for
each $10\leq N\leq 1000$. The policy set
$P=\cup_{i=0}^{N-1}\\{(P_{i},``allow")\\}$ where each $P_{i}$ was defined to
be the static string $``a1b2c3d4e5/i"$. The policy set
$Q=\cup_{i=0}^{N-1}\\{(Q_{i},``allow")\\}$ where each $Q_{i}$ is defined as
the string $``a1b2c3d4e5/i*"$ ending in the wildcard character. For example,
if $N=2$, $P=\\{``a1b2c3d4e5/1",``a1b2c3d4e5/2"\\}$ and
$Q=\\{``a1b2c3d4e5/1*",``a1b2c3d4e5/2*"\\}$. In this case, there are 2
policies in $P$ and two policies in $Q$.

We varied N and measured the data load, SMT encoding, and $P\implies Q$ times
for Z3 as well as for cvc5. Note $Q\implies P$ is not valid. In Figure 3, we
observe that Z3 was faster than cvc5 in total time and, in particular, in
proving $P\implies Q$, Z3 was often an order of magnitude or more faster. Both
backends follow the same pattern where data load and SMT encoding times are
less than implication prove time. Z3 shows good performance even for $N=1000$,
which is 1000 policies in $P$ and in $Q$.

(a)

(b)

Figure 3: String with Wildcard Policy type Scalability

###  IV-C Performance Cliffs for SMT Solvers

We observed some performance cliffs while using Z3 and cvc5. First, consider
two simple policy sets in which the policy type has just one component, path,
of string type. Let $P={(``/sys1*",``allow")}$ and $Q={(``/*",``allow")}$.
While trying to prove $P$ is less permissive than $Q$, the Z3 backend hangs
but cvc5 is able to prove it.

Second, consider the policy sets:

$\displaystyle P=\\{(``jstubbs",``s2/home/jstubbs/*",``*",``allow"),$
$\displaystyle(``jstubbs",``s2/*",``PUT",``deny"),$
$\displaystyle(``jstubbs",``s2/*",``POST",``deny")\\}$

and

$\displaystyle Q=\\{(``jstubbs",``s2/home/jstubbs/a.out",``GET",$
$\displaystyle``allow"),$
$\displaystyle(``jstubbs",``s2/home/jstubbs/b.out",``GET",``allow")\\}$

Z3 was able to to prove $Q\implies P$ but cvc5 hangs.

##  V Related work

There have been several works on cloud-access control policies analysis using
SMT ([17], [18], [19], [20]). Our work is closely related to the approach used
in Zelkova ([17], [19]). Zelkova is an AWS policy analysis tool that verifies
AWS policies by reasoning if a policy is less or equally permissive than the
other. It encodes AWS policies to SMT formulas and uses SMT solvers, Z3, CVC,
and Z3AUTOMATA, to verify and prove the properties. Zelkova is not open-source
and cannot be extended to other policy languages. CloudSec’s approach is
similar to Zelkova and other prior works in defining a policy language and
translating policies to SMT formulas for reasoning using SMT solvers. The main
differences are that 1) CloudSec is an open-source, extensible automated
reasoning framework where users or developers can define their policy types
not restricted to cloud policies depending on their application, and 2)
developers can plug different SMT solvers into CloudSec’s extensible backend.
Additionally, by defining a policy converter, CloudSec can be easily
integrated into existing cloud-hosted services, as demonstrated in section
III-F.

Eiers et al. [20] proposed a framework to quantify the permissiveness of
access policies using model counting constraint solvers and relative
permissiveness between the policies. They also built an open-source tool,
QUACKY, that analyzes AWS and Azure policies. The CloudSec framework focuses
on easy extensibility, defining different policy types, and making the
reasoning tool more accessible to users. We envision that QUACKY could
potentially be a component in the CloudSec framework to compute relative
permissiveness.

Several works have studied the verification of network access control,
connectivity, and configuration policies. Jayaraman et al. ([21], [22])
proposed and built a tool called SECGURU that automatically validates network
connectivity policies using SMT bit vector theory and the Z3 solver. SECGURU
is a closed source tool used in Azure. Fogel et al. [23] proposed and
developed an open-source tool, Batfish, that analyzes network configuration
and detects errors. Campion [24] is another open-source tool for debugging
router configuration and has been implemented as an extension to Batfish. It
localizes crucial errors to relevant configuration lines. Beckett et al. [25]
proposed a general approach for network configuration that translates both
control and data plane behaviors into a logical formula and use SMT solver,
Z3, to verify the properties. They have implemented this approach in the tool
called Minesweeper. CloudSec could be extended to support network access
policies such as Firewall and router policies.

##  VI Conclusion and Future Work

In this paper, we presented a description of the CloudSec library, which
simplifies the use of SMT in analyzing security policies in real-world
systems. We applied CloudSec to the Tapis API platform to analyze thousands of
permissions records at once. In the future, we plan to incorporate CloudSec
into a public API within Tapis, allowing any user to easily submit security
analysis jobs using HTTP requests. Further, we will explore adding support for
additional backends to the project and applying CloudSec to additional real-
world systems, such as AWS, and Kubernetes.

## References

  * [1] AWS IAM. (2022, Dec.) AWS IAM. [Online]. Available: https://docs.aws.amazon.com/IAM/latest/UserGuide/access.html
  * [2] Google IAM. (2022, Dec.) Google IAM. [Online]. Available: https://cloud.google.com/iam/
  * [3] AzureRBAC. (2022, Dec.) AzureRBAC. [Online]. Available: https://learn.microsoft.com/en-us/azure/role-based-access-control/overview
  * [4] Kubernetes. (2023, May) Kubernetes RBAC. [Online]. Available: https://kubernetes.io/docs/reference/access-authn-authz/rbac/
  * [5] Casbin. (2022, Dec.) Casbin. [Online]. Available: https://casbin.org/
  * [6] KeyCloak. (2022, Dec.) KeyCloak. [Online]. Available: https://www.keycloak.org/
  * [7] Open Policy Agent. (2022, Dec.) Open Policy Agent. [Online]. Available: https://www.openpolicyagent.org/
  * [8] A. R. Bradley and Z. Manna, _The Calculus of Computation: Decision Procedures with Applications to Verification_. Springer, 2017.
  * [9] D. Kroening and O. Strichman, _Decision Procedures: An Algorithmic Point of View_ , ser. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2017.
  * [10] “CloudSec,” (Date last accessed May-21-2023). [Online]. Available: https://github.com/applyfmsec/cloudsec
  * [11] L. de Moura and N. Bjørner, “Z3: An efficient smt solver,” in _Tools and Algorithms for the Construction and Analysis of Systems_ , C. R. Ramakrishnan and J. Rehof, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 337–340.
  * [12] “Z3,” (Date last accessed 4-December-2022). [Online]. Available: https://github.com/Z3Prover/z3
  * [13] “CVC5: An efficient open-source automatic theorem prover for satisfiability modulo theories (SMT) problems.” (Date last accessed 4-December-2022). [Online]. Available: https://cvc5.github.io/
  * [14] H. Barbosa, C. W. Barrett, M. Brain, G. Kremer, H. Lachnitt, M. Mann, A. Mohamed, M. Mohamed, A. Niemetz, A. Nötzli, A. Ozdemir, M. Preiner, A. Reynolds, Y. Sheng, C. Tinelli, and Y. Zohar, “cvc5: A versatile and industrial-strength SMT solver,” in _Tools and Algorithms for the Construction and Analysis of Systems - 28th International Conference, TACAS 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Munich, Germany, April 2-7, 2022, Proceedings, Part I_ , ser. Lecture Notes in Computer Science, D. Fisman and G. Rosu, Eds., vol. 13243. Springer, 2022, pp. 415–442.
  * [15] J. Stubbs, R. Cardone, M. Packard, A. Jamthe, S. Padhy, S. Terry, J. Looney, J. Meiring, S. Black, M. Dahan, S. Cleveland, and G. Jacobs, “Tapis: An API Platform for Reproducible, Distributed Computational Research,” in _Advances in Information and Communication FICC 2021_. Springer International Publishing, 2021, pp. 878–900.
  * [16] Tapis. (2022, Dec.) Tapis permissions. [Online]. Available: https://tapis.readthedocs.io/en/latest/technical/security.html#id3
  * [17] J. Backes, P. Bolignano, B. Cook, C. Dodge, A. Gacek, K. Luckow, N. Rungta, O. Tkachuk, and C. Varming, “Semantic-based automated reasoning for aws access policies using smt,” in _2018 Formal Methods in Computer Aided Design (FMCAD)_ , 2018, pp. 1–9.
  * [18] A. Liu, X. Du, N. Wang, X. Wang, X. Wu, and J. Zhou, “Implement security analysis of access control policy based on constraint by smt,” in _2022 IEEE 5th International Conference on Electronics Technology (ICET)_ , 2022, pp. 1043–1049.
  * [19] N. Rungta, “A billion smt queries a day (invited paper),” in _Computer Aided Verification_ , S. Shoham and Y. Vizel, Eds. Cham: Springer International Publishing, 2022, pp. 3–18.
  * [20] W. Eiers, G. Sankaran, A. Li, E. O’Mahony, B. Prince, and T. Bultan, “Quantifying permissiveness of access control policies,” in _Proceedings of the 44th International Conference on Software Engineering_ , ser. ICSE ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 1805–1817. [Online]. Available: https://doi.org/10.1145/3510003.3510233
  * [21] K. Jayaraman, N. Bjørner, G. Outhred, and C. Kaufman, “Automated analysis and debugging of network connectivity policies,” Microsoft, Tech. Rep. MSR-TR-2014-102, July 2014.
  * [22] K. Jayaraman, N. Bjørner, J. Padhye, A. Agrawal, A. Bhargava, P.-A. C. Bissonnette, S. Foster, A. Helwer, M. Kasten, I. Lee, A. Namdhari, H. Niaz, A. Parkhi, H. Pinnamraju, A. Power, N. M. Raje, and P. Sharma, “Validating datacenters at scale,” in _Proceedings of the ACM Special Interest Group on Data Communication_ , ser. SIGCOMM ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 200–213. [Online]. Available: https://doi.org/10.1145/3341302.3342094
  * [23] A. Fogel, S. Fung, L. Pedrosa, M. Walraed-Sullivan, R. Govindan, R. Mahajan, and T. Millstein, “A general approach to network configuration analysis,” in _Proceedings of the 12th USENIX Conference on Networked Systems Design and Implementation_ , ser. NSDI’15. USA: USENIX Association, 2015, p. 469–483.
  * [24] A. Tang, S. K. R. Kakarla, R. Beckett, E. Zhai, M. Brown, T. Millstein, Y. Tamir, and G. Varghese, “Campion: Debugging router configuration differences,” in _Proceedings of the 2021 ACM SIGCOMM 2021 Conference_ , ser. SIGCOMM ’21. New York, NY, USA: Association for Computing Machinery, 2021, p. 748–761. [Online]. Available: https://doi.org/10.1145/3452296.3472925
  * [25] R. Beckett, A. Gupta, R. Mahajan, and D. Walker, “A general approach to network configuration verification,” in _Proceedings of the Conference of the ACM Special Interest Group on Data Communication_ , ser. SIGCOMM ’17. New York, NY, USA: Association for Computing Machinery, 2017, p. 155–168. [Online]. Available: https://doi.org/10.1145/3098822.3098834