# Greybox Penetration Testing on Cloud Access Control with
IAM Modeling and Deep Reinforcement Learning

Yang Hu∗ The University of Texas at AustinAustinTexasUSA<EMAIL_ADDRESS>,
Wenxi Wang∗ The University of Texas at AustinAustinTexasUSA<EMAIL_ADDRESS>and  Mohit Tiwari  The University of Texas at AustinAustinTexasUSA
<EMAIL_ADDRESS>
###### Abstract.

Identity and Access Management (IAM) is an access control service in cloud
platforms. To securely manage cloud resources, customers are required to
configure IAM to specify the access control rules for their cloud
organizations. However, IAM misconfiguration may be exploited to perform
privilege escalation attacks, which can cause severe economic loss. To detect
privilege escalations due to IAM misconfigurations, existing third-party cloud
security services apply whitebox penetration testing techniques, which require
the access of complete IAM configurations. This requirement might cause
problems such as information disclosure and anonymization.

To mitigate the limitation, we propose a greybox penetration testing approach
called TAC for third-party services to detect IAM privilege escalations,
without requiring the access of complete IAM configurations. The idea is to
intelligently query a limited amount of information that is only related to
IAM privilege escalation detection. Cloud customers are allowed to specify
which entities such as users and services (automatically anonymized by TAC) in
their IAM configurations can be queried, and also limit the maximum number of
queries. To realize the idea, we 1) propose abstract IAM modeling to detect
IAM privilege escalations based on the collected partial information; 2) apply
Reinforcement Learning (RL) with Graph Neural Networks (GNNs) to learn to make
as few queries as possible. To pretrain and evaluate TAC with enough diverse
tasks, we propose an IAM privilege escalation task generator called IAMVulGen.
Experimental results show that TAC detects IAM privilege escalations with
significantly lower false negative rates than baselines with high query
efficiency, on both our task set and the only publicly available privilege
escalation task set called IAM Vulnerable.

* these authors contributed equally to this work.

##  1\. Introduction

IAM (AWS, 2023b) refers to an access control service in cloud platforms. It
aims to securely manage the access to resources based on an IAM
_configuration_ specified by cloud customers with the access control rules in
their cloud organizations. An IAM configuration consists of two components:
entities (e.g., users and services such as Amazon EC2 instances) and
permissions. Given a service request and an IAM configuration, IAM is able to
check if the request obeys or violates the IAM configuration, and decide if
the request should be allowed or denied.

Therefore, the correctness of IAM configurations plays an essential role in
the effectiveness of the cloud access control. Incorrect IAM configurations,
namely IAM _misconfigurations_ , can cause adverse security consequences such
as data breaches, denial of services and resource hijacking (One, 2022;
Pernetf, 2021; Quist, 2021; Morag, 2021; Cybersecurity Insiders, 2021), which
have led to trillions of dollars loss worldwide in recent years (DivvyCloud,
2020). IAM privilege escalation (Gietzen, 2018; Kleijn, 2022; Kedrosky, 2022)
is an attack towards cloud access control which exploits the IAM design flaw
to obtain additional permissions for performing sensitive operations or
accessing sensitive data/resources. One of the most common ways to realize IAM
privilege escalations is to exploit IAM misconfigurations: the misconfigured
IAM may allow the attacker to modify its configuration so that the attacker is
allowed by the modified IAM configuration to obtain additional permissions.
There is a famous real-world IAM privilege escalation due to misconfiguration
in 2019 (One, 2022), leaking about 100 million credit card information in a
US-based financial institute (details are illustrated in Section 3.1.2).

To mitigate this issue, several cloud security services have been released to
detect privilege escalations due to IAM misconfigurations. There are two kinds
of services: 1) _native_ cloud security services (Rungta, 2022; AWS, 2023h;
Backes et al., 2018; Bouchet et al., 2020; AWS, 2023g, d) provided by cloud
providers, and 2) _third-party_ cloud security services provided by cloud
security startups, labs, open-source organizations, etc (Alliance, 2021).
Native services usually aim to provide basic security guarantees for cloud
customers, while third-party services aim to provide specialized security
guarantees for cloud customers with complex and diverse demands (Sehgal,
2021).

In this paper, we focus on third-party cloud security services for detecting
privilege escalations due to IAM misconfigurations. To our knowledge, all
existing third-party services apply _whitebox_ penetration testing techniques
(Lab, 2022; Group, 2023; Salesforce, 2022; Labs, 2022), which require the
access of complete IAM configurations. However, cloud customers are usually
reluctant to share their complete configurations, which would disclose
sensitive information of their cloud organizations. In practice, they usually
have to anonymize their IAM configurations before using third-party services,
which requires lots of manual effort, and may reduce the detection accuracy of
the whitebox penetration testing.

To mitigate the limitation of whitebox penetration testing, we propose a
precise _greybox_ penetration testing approach called TAC
(Testing Access Control) to detect IAM privilege escalations based on limited
information of IAM configurations. The idea is to have an intelligent _query_
mechanism to send queries which are simulated requests to collect a limited
amount of permission assignment information (i.e., which entity in the IAM
configuration is assigned with which permission). To avoid excessive
information leakage, TAC allows the cloud customers to 1) specify which
entities (automatically anonymized by TAC) in their IAM configurations are
allowed to be queried with the permission assignment information, namely the
_configuration visibility_ ; 2) limit the maximum amount of queries, namely
the _query budget_.

To achieve the greybox penetration testing with the intelligent query
mechanism, TAC needs to overcome two challenges: 1) detecting privilege
escalations based on partial information of IAM configurations collected by
queries, and 2) learning to generate as few queries as possible to perform the
detection within the query budget. To overcome the first one, we propose
abstract modeling for IAM configurations based on the defined Permission Flow
Graph with predefined abstract states and rules for updating the configuration
with partial information provided by the queries. To overcome the second one,
we formulate our problem into an RL problem, and apply GNN-based deep RL with
pretraining to solve the problem.

To the best of our knowledge, there is only one publicly available IAM
privilege escalation task set called IAM Vulnerable (Art, 2021a) containing
only 31 tasks. However, the pretraining and evaluation of TAC require a large
number of diverse tasks. Regarding this, we propose our task generator called
IAMVulGen which can randomly generate IAM privilege escalation tasks from a
large entity and permission space with diverse types manually identified from
AWS official documentations (AWS, 2023c, f, b) and studies on IAM privilege
escalations (Gietzen, 2018; Kleijn, 2022; Kedrosky, 2022; Xscaler, 2021).

In our experiments, for dataset, we apply IAMVulGen to generate a pretraining
set containing 500 tasks and a testing set containing another 500 tasks. For
baselines, since there is no existing greybox or blackbox IAM penetration
testing tools that we are aware of, we adapt three state-of-the-art whitebox
IAM penetration testing tools, namely Pacu (Lab, 2022), Cloudsplaining
(Salesforce, 2022) and PMapper (Group, 2023) into three greybox testing tools,
namely Q-Pacu, Q-Cloud and Q-PMapper, respectively. In addition, to understand
how the proposed RL approach performs, we also build three variants of TAC.

Experimental results show that TAC performs with the lowest false negative
rates than all baselines on our testing set under all seven predefined small
query budgets. In addition, TAC consumes significantly fewer queries than its
three variants on our testing set, showing the superiority of our RL-based
query strategy. Furthermore, for the only publicly available task set IAM
Vulnerable (Art, 2021a), TAC is able to detect 23 privilege escalation tasks
under a query budget of 10, and all 31 tasks with a query budget of 20, which
significantly outperforms Q-Pacu, Q-Cloud and Q-PMapper which detect no more
than 15 tasks. The contributions of this paper are:
Approach. To our knowledge, TAC is the first greybox penetration testing tool
for third-party cloud security services to detect IAM privilege escalations
due to IAM misconfigurations.
Implementation. TAC is implemented as a prototype for AWS. An IAM privilege
escalation task generator IAMVulGen is also implemented to facilitate TAC’s
training and evaluation.
Evaluation. TAC is evaluated on our task set and IAM Vulnerable. Results show
that TAC detects IAM privilege escalations with significantly low false
negative rate and high query efficiency.

##  2\. Related Work

For IAM privilege escalation detection, third-party cloud security teams only
focus on building whitebox cloud penetration testing tools. These tools can be
classified into two kinds: the _pattern-based_ approach and the _graph-based_
approach. For the pattern-based approach, Gietzen was the first to identify
$21$ typical IAM privilege escalation patterns(Gietzen, 2018). Two whitebox
detectors Pacu (Lab, 2022) and Cloudsplaining (Salesforce, 2022) select
relevant privilege escalation patterns identified by Gietzen to discover the
IAM privilege escalations. However, these tools do not support detecting
_transitive privilege escalations_ (i.e., attackers gain sensitive permissions
indirectly through intermediate entities) (Art, 2021b).

Graph-based approaches are proposed to mitigate this limitation. PMapper
(Group, 2023) models the authentication relation between users/roles (i.e.,
whether a user/role can be authenticated as another user/role through
permissions) in an IAM configuration as a directed graph. With the graph
modeling, PMapper detects transitive privilege escalations by checking if a
non-admin user/role can be authenticated as an admin user. AWSPX (Labs, 2022)
applies similar graph modeling, and further visualizes the detected privilege
escalations. Existing graph-based approaches have two limitations: 1) the
graph modeling considers only authentications between users/roles, ignoring
possible privilege escalations among other entity types (e.g., services) or
caused by non-authentication strategies (e.g., changing the default version of
an IAM policy (AWS, 2023a)); 2) they ignore the fact that privilege
escalations can be realized by obtaining sensitive permissions from non-admin
entities.

TAC models the IAM configuration based on our defined permission flow graph
which is more comprehensive for detecting privilege escalations w.r.t. both
admin and non-admin entities with all possible types. Furthermore, as a
greybox penetration testing tool, TAC detects privilege escalations using
partial information of an IAM configuration through abstract graph-based
modeling.

##  3\. IAM Modeling

We first introduce the basics of IAM configurations and privilege escalations
on IAM (Section 3.1). We then present our _concrete IAM modeling_ using the
proposed _Permission Flow Graph_ (PFG) (Section 3.2). Based on the concrete
modeling, we further propose our _abstract IAM modeling_ , which provides the
foundation of our greybox penetration testing (Section 3.3).

###  3.1. Preliminaries

####  3.1.1. IAM Configuration

IAM configuration consists of three components: subjects, roles and
permissions. Subjects (i.e., users, user groups and services) can actively
perform actions. Permissions refer to privileges of performing operations.
Roles are created to represent job functions, responsibilities, and privileges
within an organization. A subject/role in an IAM configuration can obtain
permissions in both direct and indirect ways. Permissions can be directly
assigned to users, user groups and roles; permissions assigned to a
subject/role can be indirectly assigned to another subject/role in several
ways. For example, permissions assigned to a role can be indirectly assigned
to a user who assumes the role (i.e., become a member of the role);
permissions assigned to a user group can be indirectly assigned to a user in
the user group. Figure 1(a) shows an illustrative IAM configuration example.
User 1 and User 2 are added in a user group called Group 1. Since Perm 2 is
directly assigned to Group 1, users (i.e., User 1 and User 2) in Group 1 can
indirectly obtain Perm 2. In addition, both User 2 and Service 1 obtain Perm 3
indirectly by assuming Role 2.

(a) IAM configuration.

(b) IAM privilege escalation.

Figure 1. Illustrative examples of IAM configuration and IAM privilege
escalation.

####  3.1.2. Privilege Escalations due to IAM Misconfiguration

The privilege escalation on IAM (Gietzen, 2018; Kleijn, 2022; Kedrosky, 2022)
is the act of exploiting the IAM design flaw to obtain additional permission
for performing the sensitive operation or accessing sensitive data/resources.
The misconfigured IAM may allow the attacker to change its configuration so
that the attacker is allowed by the modified IAM configuration to obtain
additional sensitive permission.

Figure 1(b) shows a privilege escalation due to the illustrative IAM
misconfiguration example in Figure 1(a), which is derived from the famous
real-world IAM privilege escalation in 2019 (mentioned in Section 1). Service
1 is compromised by the attacker, Perm 1 is the permission that the attacker
targets to obtain, and Perm 3 is the permission of assuming Role 1. To obtain
the permission Perm 1, the compromised Service 1 may use Perm 3 to assume Role
1 (represented as a red line in Figure 1(b)). Since Role 1 is assigned with
Perm 1, the compromised Service 1 will be indirectly assigned with Perm 1 by
assuming Role 1.

###  3.2. Concrete IAM Modeling

(a) The concrete PFG.

(b) The concrete IAM modeling.

(c) The visible concrete PFG.

Figure 2. PFGs of the example shown in Figure 1(a). Permission flows with
enabled states are annotated in green; with disabled states are annotated in
red; with unknown states are annotated in black.

####  3.2.1. PFG

To present PFG, we introduce two new terms: _entity_ and _permission flow_. An
entity represents either a subject or a role in an IAM configuration. For
example, Group 1, User 1, User 2, Service 1, Role 1 and Role 2 are the
entities of the illustrative IAM configuration shown in Figure 1(a). A
permission flow models an indirect permission assignment from one entity to
another. Note that whether there is a permission flow between two entities
depends on the types of the two entities. Details about identifying permission
flows between entities is introduced in Section 4.4. Each permission flow has
a _flow state_ representing whether the permission flow is currently enabled
or disabled. If a permission flow from entity $e_{1}$ to entity $e_{2}$ is
enabled, all permissions assigned to $e_{1}$ can be automatically assigned to
$e_{2}$; otherwise (i.e., the permission flow state is disabled), the
permissions cannot be automatically assigned.

Next, we define the permission space $P$. We identify two types of permissions
which can be utilized by the compromised entity to possibly obtain the target
permission. We call them Type-I and Type-II permissions. We will introduce the
two types of permissions in detail in Section 3.3.1. Our permission space $P$
consists of all Type-I permissions (denoted as $P_{\texttt{I}}$), all Type-II
permissions (denoted as $P_{\texttt{II}}$) and the target permission (if the
target permission is neither the Type-I nor Type-II permission).

Now, we introduce our PFG to concretely model an IAM configuration. A PFG
includes entities as its nodes and permission flows as its edges. Formally, a
PFG is defined as a tuple $G=(E,F,\mathcal{A},\mathcal{W})$, where $E$ denotes
the entity space; $F\subseteq E\times E$ denotes a set of permission flows;
$\mathcal{A}:E\mapsto 2^{P}$ denotes a permission assignment function which
maps an entity to a set of permissions;
$\mathcal{W}:F\mapsto\\{\texttt{true},\texttt{false}\\}$ denotes a concrete
flow state function which outputs whether a permission flow is currently
enabled (denoted as true) or disabled (denoted as false). Figure 2(a) shows a
PFG which straightforwardly models the IAM configuration example shown in
Figure 1(a). Three entities (i.e., Group 1, Role 1 and Role 2) are directly
assigned with permissions. Three enabled permission flows (highlighted in
green) represents indirect permission assignments.

####  3.2.2. Permission Flow Function

Given a PFG $G=(E,F,\mathcal{A},\mathcal{W})$, we define the permission flow
function returning a new PFG
$G^{\prime}=(E,F,\mathcal{A}^{\prime},\mathcal{W})$ by performing one
permission flow iteration. The permission flow function $\mathcal{M}$ is
defined as $G^{\prime}=\mathcal{M}(G)$ where

$\mathcal{A}^{\prime}({e_{2}})=\bigcup_{\\{(e_{1},e_{2})\in
F|\mathcal{W}(e_{1},e_{2})=\texttt{true}\\}}\mathcal{A}(e_{1})\cup\mathcal{A}(e_{2})$

meaning that, for each entity $e_{2}$, all permissions of the entities which
have enabled permission flows to $e_{2}$ are assigned to $e_{2}$.

####  3.2.3. Concrete IAM Configuration Modeling

Given a PFG $G$, we perform the fixed point iteration w.r.t. the permission
flow function $\mathcal{M}$ on $G$. The resulting PFG denoted as $G^{\prime}$
is our concrete model of the IAM configuration. Formally,
$G^{\prime}=\mathcal{M}^{*}(G)$, where $\mathcal{M}^{*}$ refers to the fixed
point iteration of $\mathcal{M}$ (i.e.,
$\mathcal{M}^{*}(G)=\mathcal{M}^{n}(G)$ s.t.
$\mathcal{M}^{n}(G)=\mathcal{M}^{n-1}(G)$). Figure 2(b) shows a concrete
modeling of the illustrative IAM configuration example shown in Figure 1(a),
which is the fixed point of the PFG in Figure 2(a). Based on five enabled
permission flows, the PFG is updated with indirect permission assignments:
Entity 2 and Entity 3 indirectly obtain Perm 2 from Entity 1; Entity 3 and
Entity 6 indirectly obtain Perm 3 from Entity 5; Entity 2 indirectly obtains
Perm 1 and Perm 2 from Entity 4. The resulting PFG cannot be updated further
by any indirect permission assignments, which is taken as the fixed point.

####  3.2.4. Concrete Privilege Escalation Detection

To introduce how we concretely model the privilege escalation of a given IAM
configuration, we first introduce two new terms: the _compromised entity_
which is the entity controlled by the attacker, and the _target permission_
which is the permission that the attacker tries to make the compromised entity
to obtain. According to the privilege escalation example shown in Figure 1(b),
Service 1, which is Entity 6 in the concrete modeling shown in Figure 2(b), is
a compromised entity; Perm 1 is the target permission.

An IAM configuration has a _privilege escalation_ iff the compromised entity
can obtain the target permission through the permissions assigned to the
compromised entity. Formally, let
$G_{0}=(E_{0},F_{0},\mathcal{A}_{0},\mathcal{W}_{0})$ be an initial IAM
configuration, $u$ be the compromised entity, and $l\in
P\setminus\mathcal{A}_{0}(u)$ be a target permission; the concrete IAM
configuration $G_{0}$ has a privilege escalation iff there exists a sequence
of permissions $p_{1},\ldots,p_{n},$ where $p_{i}\in\mathcal{A}_{i-1}(u)$, and
a modified IAM configuration
$G_{n}=(E_{n},F_{n},\mathcal{A}_{n},\mathcal{W}_{n})$ such that

$G_{0}\overset{p_{1}}{\hookrightarrow}G_{1}\ldots\overset{p_{n}}{\hookrightarrow}G_{n}\land
l\in\mathcal{A}_{n}(u),$

where $G_{i-1}\overset{p_{i}}{\hookrightarrow}G_{i}$ annotates that the
concrete IAM configuration $G_{i-1}$ is modified to $G_{i}$ by the compromised
entity $u$ through the permission $p_{i}\in\mathcal{A}_{i-1}(u)$.

###  3.3. Abstract IAM Modeling

Concrete privilege escalation modeling requires a complete IAM configuration,
which may cost much anonymization effort. To address this issue, TAC allows
cloud customers to specify their IAM configuration visibility. In detail,
cloud customers are able to choose a subset of entities and the permission
flows among them to be visible to TAC. Note that each visible entity is
automatically anonymized as a randomly generated entity ID, except that the
compromised entity type is needed by TAC (how such entity type information is
utilized by TAC is introduced in Section 4.3.3). In sum, only IDs of visible
entities, permission flows with unknown states among these entities, and the
compromised entity type are accessible information to TAC. Figure 2(c) shows
the visible information of the concrete IAM configuration model (shown in
Figure 2(b)) to TAC.

To detect privilege escalations using such limited prior knowledge of an IAM
configuration, TAC sends queries to obtain only necessary permission
assignment information among visible entities. We propose abstract IAM
modeling for the query-based privilege escalation detection, which provides
the foundation of TAC.

####  3.3.1. Abstract PFG

As mentioned in Section 3.2.1, Type-I and Type-II permissions can help the
compromised entity to obtain the target permission. Specifically, a Type-I
permission, if being assigned to an entity, allows it to enable a permission
flow; a Type-II permission $s$, if being assigned to an entity, allows the
entity to directly assign a target permission or a Type-I permission $t_{s}$
to an entity $e_{s}$. For example, the permission adding a user to a user
group is a Type-I permission. The permission attaching an IAM policy to a user
is a Type-II permission, as it directly assigns each permission in the policy
to the user.

To simplify the abstract modeling, we convert each Type-II permission into a
Type-I permission. For each Type-II permission $s$, we 1) add a _pseudo
entity_ $\beta_{s}$ assigned with the corresponding target or Type-I
permission $t_{s}$, and 2) add the _pseudo permission flow_ from the pseudo
entity $\beta_{s}$ to the corresponding entity $e_{s}$. This way, each Type-II
permission $s$ becomes a Type-I permission which allows the assigned entity to
enable the pseudo permission flow from the pseudo entity $\beta_{s}$ to the
corresponding entity $e_{s}$. To this end, we define our abstract entity space
$\hat{E}$ and abstract permission flow space $\hat{F}$ by extending the
visible entity space $E_{\mathtt{vis}}\subseteq E$ and the visible permission
flow space $F_{\mathtt{vis}}\subseteq F$, with the pseudo entities and pseudo
permission flows, respectively. Formally,
$\hat{E}=E_{\mathtt{vis}}\cup\\{\beta_{s}|s\in P_{\texttt{II}}\land e_{s}\in
E_{\mathtt{vis}}\\}$, and
$\hat{F}=F_{\mathtt{vis}}\cup\\{(\beta_{s},e_{s})|s\in P_{\texttt{II}}\land
e_{s}\in E_{\mathtt{vis}}\\}$.

Next we define our abstract entity-permission state function
$\hat{\mathcal{A}}:\hat{E}\times P\mapsto\\{?,+\\}$ maps each entity-
permission pair to an abstract state. $\hat{\mathcal{A}}(e,p)=?$ means that it
is unknown whether the permission $p$ can be assigned to the entity $e$ or
not; $\hat{\mathcal{A}}(e,p)=+$ means that the permission $p$ can be assigned
to the entity $e$, either directly or indirectly. Initially, the entity-
permission state function assigns $?$ to all entity-permission pairs except
for the pairs of each pseudo entity and the corresponding Type-I or target
permission (involved in the Type-II permission). Formally, the initial
abstract entity-permission state function $\hat{\mathcal{A}}_{init}(e,p)$ is
defined as

$\hat{\mathcal{A}}_{init}(e,p)=\begin{cases}+,&\exists s\in
P_{\texttt{II}}.e=\beta_{s}\land p=t_{s},\\\ ?,&otherwise.\end{cases}$

The abstract permission flow state function
$\hat{\mathcal{W}}:\hat{F}\mapsto\\{*,\oplus\\}$ maps each permission flow to
an abstract state. $\hat{\mathcal{W}}(f)=*$ means that it is unknown whether
the permission flow $f$ can be enabled or not; 2)
$\hat{\mathcal{W}}(f)=\oplus$ means that the permission flow can be enabled.
Initially, the states of all permission flows are mapped to $*$, which is
defined as

$\forall f\in\hat{F}.~{}\hat{\mathcal{W}}_{init}(f)=*$

We define our abstract PFG as a tuple
$\hat{G}=(\hat{E},\hat{F},\hat{\mathcal{A}},\hat{\mathcal{W}})$. Figure 3(a)
shows an example of an initial abstract PFG
$\hat{G}_{init}=(\hat{E},\hat{F},\\\
\hat{\mathcal{A}}_{init},\hat{\mathcal{W}}_{init})$, which is the abstract
modeling of the visible concrete PFG example shown in Figure 2(c). The
permission space $P$ of the initial abstract PFG example includes three
permissions Perm 1, Perm 2 and Perm 3. Consider that Perm 2 is the only Type-
II permission which allows its assigned entity to directly assign the target
permission Perm 1 to Entity 4. Perm 2 is converted into the Type-I permission
with the added pseudo permission flow from the pseudo entity Entity
$\beta_{perm2}$ to Entity 4. All entity-permission states are initialized to
$?$, except for the state of the pseudo entity Entity $\beta_{perm2}$ and the
target permission Perm 1 (involved in the Type-II permission Perm 2) being
initialized to $+$; all permission flow states are initialized to $*$.

(a) The initial abstract IAM configuration representing the visible concrete
PFG in Figure 2(c).

(b) The intermediate abstract IAM configuration updated with the information
provided by the query oracle
$\mathcal{O}(\texttt{Entity~{}6},\texttt{Perm~{}3})$

(c) The terminal abstract IAM configuration updated with the information
provided by the query oracle
$\mathcal{O}(\texttt{Entity~{}4},\texttt{Perm~{}1})$

Figure 3. The query-based privilege escalation detection.

####  3.3.2. Abstract Permission Flow Function

Given an abstract PFG
$\hat{G}=(\hat{E},\hat{F},\hat{\mathcal{A}},\hat{\mathcal{W}})$, the abstract
permission flow function $\hat{\mathcal{M}}$ outputs a new PFG
$\hat{G}^{\prime}=(\hat{E},\hat{F},\hat{\mathcal{A}}^{\prime},\hat{\mathcal{W}^{\prime}})$
by performing one permission flow iteration. Formally, the function is defined
as $\hat{G}^{\prime}=\hat{\mathcal{M}}(\hat{G})$, where

$\small\hat{\mathcal{A}}^{\prime}(e,p)=\begin{cases}+,&\textbf{C1:}~{}\exists
e^{\prime}\in N_{\oplus}^{(e)}.\hat{\mathcal{A}}(e^{\prime},p)=+,\\\
\hat{\mathcal{A}}({e}),&otherwise.\\\ \end{cases}$

$\small\hat{\mathcal{W}}^{\prime}(f)=\begin{cases}\oplus,&\textbf{C2:}~{}\exists
p\in P_{\texttt{I}}.\llbracket p\rrbracket=f\land\hat{\mathcal{A}}(u,p)=+,\\\
\hat{\mathcal{W}}(f),&otherwise.\\\ \end{cases}$

Here,
$N_{\oplus}^{(e)}=\\{e^{\prime}|(e^{\prime},e)\in\hat{F}\land\hat{\mathcal{W}}(e^{\prime},e)=\oplus\\}$;
$\llbracket p\rrbracket$ refers to the permission flow that can be enabled
with the Type-I permission $p$.

The condition C1 is used to update the abstract state of an entity-permission
pair. If there exists an entity $e^{\prime}$ having the permission $p$ (i.e.,
the abstract state is $+$) and an enabled permission flow (i.e., the
permission flow state is $\oplus$) from the entity $e^{\prime}$ to an entity
$e$, then $e$ can have the permission $p$ (i.e., the abstract state of the
pair $(e,p)$ is updated to $+$). Figure 4(a) illustrates how the abstract
state of an entity-permission pair gets updated under the condition C1.

The condition C2 is used to update the abstract state of a permission flow. If
there exists a permission $p$ assigned to the compromised entity $u$ (i.e.,
the abstract state of the pair $(u,p)$ is $+$) and the permission $p$ is a
Type-I permission which allows to enable a permission flow $f$, then the
permission flow $f$ can be enabled (i.e., the abstract state of $f$ is updated
to $\oplus$). Figure 4(b) illustrates how the abstract state of a permission
flow gets updated under the condition C2.

(a) State update under C1

(b) State update under C2.

Figure 4. An illustration of the abstract entity-permission state update and
the abstract permission flow state update.

####  3.3.3. Abstract IAM Configuration Modeling

Similar with the concrete IAM configuration modeling, given an abstract PFG
$\hat{G}$, we perform the fixed point iteration w.r.t. the abstract permission
flow function $\hat{\mathcal{M}}$ on $\hat{G}$. The resulting
$\hat{G}^{\prime}$ is our abstract model of the IAM configuration. Formally,
$\hat{G}^{\prime}=\hat{\mathcal{M}}^{*}(\hat{G})$ where
$\hat{\mathcal{M}}^{*}$ refers to the fixed point iteration of
$\hat{\mathcal{M}}$ (i.e., $\hat{\mathcal{M}}^{*}(G)=\hat{\mathcal{M}}^{n}(G)$
such that $\hat{\mathcal{M}}^{n}(G)=\hat{\mathcal{M}}^{n-1}(G)$).

In particular, the initial abstract PFG
$\hat{G}_{init}=(\hat{E},\hat{F},\hat{\mathcal{A}}_{init},\hat{\mathcal{W}}_{init})$
(introduced in Section 3.3.1) is the initial abstract IAM configuration. In
addition,
$\hat{G}_{term}=(\hat{E},\hat{F},\hat{\mathcal{A}}_{term},\hat{\mathcal{W}}_{term})$
denotes the _terminal_ abstract IAM configuration, where
$\hat{\mathcal{A}}_{term}(u,l)=+$. The rest configurations are referred to as
_intermediate_ abstract IAM configurations. Figure 3 shows three abstract IAM
configurations abstracting the partially visible PFG shown in Figure 2(c),
including an initial abstract configuration (Figure 3(a)), an intermediate
abstract configuration (Figure 3(b)) and a terminal abstract configuration
(Figure 3(c)).

####  3.3.4. Query-based Privilege Escalation Detection

For query-based privilege escalation detection on the abstract IAM
configuration, we first need a _query oracle_ to provide TAC with the
permission assignment information of the concrete IAM configuration. Given a
query (i.e., an entity-permission pair), the query oracle outputs if the
permission is initially assigned to the entity in the concrete configuration.
Formally, let $Q=E\times P$ be the query space. A query oracle w.r.t. a
concrete IAM configuration $G=(E,F,\mathcal{A},\mathcal{W})$ is defined as a
function $\mathcal{O}:Q\mapsto\\{\texttt{true},\texttt{false}\\}$ satisfying

$\mathcal{O}(e,p)=\begin{cases}\texttt{true},&p\in\mathcal{A}(e),\\\
\texttt{false},&p\not\in\mathcal{A}(e).\end{cases}$

An IAM configuration has a privilege escalation iff based on the information
queried from the oracle, its initial abstract configuration can be updated to
a terminal abstract configuration. Formally, let
$\hat{G}_{0}=(\hat{E}_{0},\hat{F}_{0},\hat{\mathcal{A}}_{0},\hat{\mathcal{W}}_{0})$
be an initial abstract IAM configuration, $u$ be the compromised entity, and
$l$ be the target permission. The initial abstract IAM configuration
$\hat{G}_{0}$ has an abstract privilege escalation iff there exists a sequence
of queries $(e_{1},p_{1}),\ldots,(e_{n},p_{n})\in Q$, and a terminal abstract
IAM configuration
$\hat{G}_{n}=(\hat{E}_{n},\hat{F}_{n},\hat{\mathcal{A}}_{n},\hat{\mathcal{W}}_{n})$
such that

$\hat{G}_{0}\overset{(e_{1},p_{1})}{\hookrightarrow}\hat{G}_{1}\ldots\overset{(e_{n},p_{n})}{\hookrightarrow}\hat{G}_{n}\land\hat{\mathcal{A}}_{n}(u,l)=+,$

where $\hat{G}_{i-1}\overset{(e_{i},p_{i})}{\hookrightarrow}\hat{G}_{i}$
annotates that the abstract IAM configuration $\hat{G}_{i-1}$ is updated to
$\hat{G}_{i}$ based on the oracle information of the query $(e_{i},p_{i})$:

$\hat{G}_{i}=\begin{cases}\hat{\mathcal{M}}^{*}(\hat{G}_{i-1}[\hat{\mathcal{A}}_{i-1}[e_{i},p_{i}]\mapsto+]),&\mathcal{O}(e_{i},p_{i})=\texttt{true},\\\
\hat{G}_{i-1},&otherwise.\end{cases}$

Note that our abstract IAM modeling and state updating rules guarantee the
precision of IAM privilege escalation detection, meaning that the privilege
escalation identified by TAC must be a true privilege escalation.

We illustrate our query-based privilege escalation detection with the abstract
IAM configuration examples shown in Figure 3. Given the initial abstract IAM
configuration in Figure 3(a) where the compromised entity is Entity 6, TAC may
query the query oracle whether Entity 6 initially has the permission Perm 3
(i.e., the query (Entity 6, Perm 3)). The query oracle answers yes to the
query (i.e., $\mathcal{O}(\texttt{Entity~{}6},\texttt{Perm
3})=\texttt{true}$). Thus, the abstract state of the entity-permission pair
(Entity 6, Perm 3) is updated to +. In addition, Perm 3 is the Type-I
permission which allows its assigned entity (i.e., Entity 6) to enable the
permission flow from Entity 4 to Entity 6. Thus, the abstract state of the
permission flow from Entity 4 to Entity 6 is updated to $\oplus$. The
resulting intermediate abstract IAM configuration is shown in Figure 3(b).
Next, TAC may send another query to see whether Entity 4 has the target
permission Perm 1 (i.e., the query (Entity 4, Perm 1)). As a result, the query
oracle answers yes to the query (i.e.,
$\mathcal{O}(\texttt{Entity~{}4},\texttt{Perm 1})=\texttt{true}$). Thus, the
abstract state of the entity-permission pair (Entity 4, Perm 1) is updated to
$+$. Based on the condition C1 of the abstract permission flow function
$\hat{\mathcal{M}}$, the abstract state of the entity-permission pair (Entity
6, Perm 1) is updated to $+$. Since the initial IAM configuration can be
updated to the terminal abstract IAM configuration shown in Figure 3(c), the
initial configuration has a privilege escalation.

##  4\. Greybox Penetration Testing

In the previous section, we introduced query-based privilege escalation
detection. However, sending too many queries may reveal too much information
of the IAM configurations, which can exceed the amount of information that
cloud customers are willing to share; it may be taken as a Denial-of-Service
attack, which can violate the penetration testing policy of the cloud platform
(AWS, 2023e).

To do effective and practical greybox penetration testing on IAM
configurations, we allow cloud customers to set a _query budget_ (i.e., the
maximum number of queries) for their tasks. The goal is to do the privilege
escalation detection within the query budget. As introduced in Section 3.3.4,
the problem is a _sequential decision making_ problem, where each query is
selected based on the results of previous queries. To solve the problem, we
apply RL with GNNs and model pretraining to learn to use as few queries as
possible to identify the IAM privilege escalation.

###  4.1. Preliminaries - RL Basics

RL refers to a set of algorithms which aim to learn to make decisions from
interactions (Sutton and Barto, 2020). An RL problem is usually formulated as
a Markov Decision Process (MDP). In MDP, the learner or the decision maker is
called the _RL agent_. The RL agent interacts with the _environment_ which
maintains its internal _state_. In each interaction between the RL agent and
the environment, the RL agent chooses an _action_ to perform; the environment
then updates its _state_ based on the action, and returns a _reward_
quantifying the effectiveness of the action. A discount factor ranging from 0
to 1 indicates the importance of future rewards relative to the current
reward.

In this paper, we only consider a finite sequence of interactions between the
RL agent and the environment, which are divided into several sub-sequences,
namely _episodes_. Each episode starts from an _initial state_ and ends with a
_terminal state_. If an episode ends, the state of the environment will be
automatically reset to the initial state for the next episode to start. The
_return_ refers to the cumulative rewards for one episode. The goal of the RL
agent is to learn an _RL policy_ for choosing an action per interaction which
maximizes the expected return.

###  4.2. RL Formulation

Figure 5. The general framework of TAC.

Figure 5 shows the general framework of our IAM greybox penetration testing
tool TAC. The input of TAC is 1) an initial abstract IAM configuration which
is an abstract modeling of a partial IAM configuration visible to TAC; 2) a
customer-defined query budget. The output is to report if a privilege
escalation is detected within the given query budget. We design the TAC
framework by formulating the IAM privilege escalation detection problem into
an RL problem. Every component of the RL formulation are described below:
State: a state consists of an abstract IAM configuration and a current query
budget. Particularly, an initial state consists of the initial abstract IAM
configuration and the customer defined query budget; a terminal state includes
either a zero current query budget (called Terminal 1 state) or a terminal
abstract IAM configuration (called Terminal 2 state), or both (called Terminal
3 state).
Action: an action is a query selected by the query model of the RL agent for
getting information to update the current configuration.
Reward: the reward is the output by the query reward model, which is simply
$-1$ for each query. In addition, we set the discount factor to 1, treating
current rewards and future rewards equally important. In this design,
maximizing the return is equivalent to minimizing the number of queries, which
is our learning goal.
Environment: it consists of three parts: 1) a query reward model; 2) a query-
based abstract IAM configuration update as introduced in Section 3.3; 3) a
query counter for updating the current query budget (each query decreases the
current query budget by 1).
RL Agent: An RL agent uses a _query model_ (i.e., a query RL policy) for
selecting a query based on the current state received from the environment. In
addition, the RL agent uses the classic Actor-Critic Method (Sutton and Barto,
2020) as its learning algorithm to update the query model based on the
rewards. The basic idea is to construct two separate neural networks: an actor
network and a critic network. The actor network serves as the query model,
while the critic network is used to estimate the expected return w.r.t. the
current state and generate feedback for improving the actor network. The RL
agent also has a state checker which reports the detection results based on
the terminal states (privilege escalation is reported when the state is the
Terminal 2 or Terminal 3 state; no issue is found when the state is the
Terminal 1 state).
Episode: In each episode, the RL agent starts from the initial state and
iteratively sends queries for updating the state until the terminal state is
reached.

Figure 6. The graph representation of the configuration in Figure 3(b) for GNN
(Entity 2 and Perm 3 are omitted).

###  4.3. Query Model

Note that our RL problem requires the RL agent to detect the privilege
escalation within only one episode. While classic deep RL applications usually
train an RL policy from scratch (i.e., weights in the policy model are
randomly initialized), which requires lots of episodes to maximize the return.
To address this issue, the idea is to design a good query model and pretrain
the model with multiple episodes on pretraining tasks, so that the model can
be quickly adapted into a good policy model within only one episode for new
tasks with similar kinds as the pretraining tasks.

As introduced, the query model selects queries based on current states
including abstract IAM configurations which are structured as graphs.
Therefore, we design our query model as a GNN. In the following, we first
introduce the graph representations of IAM configurations for our GNN model.
Next, we illustrate the design of the model. Last, we present how we pretrain
the query model.

####  4.3.1. The Graph Representation

Figure 6 shows the graph representation of the abstract IAM configurations
shown in Figure 3(b). The nodes in the graph representation are generally
classified into two types: entity node type and permission node type. Entity
nodes are further classified into three sub-types: pseudo entity, compromised
entity and other entities; permission nodes can be further classified into two
sub-types: target permission type and Type-I permission type (there is no
Type-II permission type, since all Type-II permissions are converted into
Type-I permissions as introduced in Section 3.3.1). Directed edges in the
graph are generally classified into two types, entity-entity type representing
permission flows, and entity-permission type including three kinds: 1) edges
representing the permission assignments from an entity to one of its assigned
permissions; 2) edges from a source entity of the permission flow in a Type-I
permission to the corresponding Type-I permission; 3) edges from a sink entity
of the permission flow in a Type-I permission to the corresponding Type-I
permission. The features of the nodes and edges include their corresponding
types. In addition, the features of edges representing the permission flows
and assignments also include their corresponding abstract values
$\hat{\mathcal{W}}$ and $\hat{\mathcal{A}}$, respectively.

Figure 7. The design and workflow of the query model.

####  4.3.2. GNN-based Model Design

Given the graph representation of the abstract IAM configuration and the
current query budget as inputs, GNN-based query model first samples an entity-
permission edge representing a permission assignment with $?$ abstract state
in the input graph based on the inferred probability distribution, and then
outputs the corresponding query of the sampled permission assignment edge. The
idea is to let the query model predict which permission assignment with the
“unknown” state is critical for the detection, given the current state of the
partial configuration.

Figure 7 illustrates the design and workflow of our GNN-based query model.
Given a graph representation of an abstract IAM configuration, shown as the
graph (A), a GNN layer consisting of five stacked Graph Attention Network
named GATv2 layers (Brody et al., 2021) is applied to generate the embedding
of the permission assignment edges, shown as the graph (B). For each
permission assignment edge, we concatenate its embedding with the normalized
current query budget (i.e., the current query budget divided by the initial
input query budget) to get a new edge embedding, shown as the graph (C). Next,
a Multi-Layer Perceptron (MLP) layer is applied to predict the probability
distribution over the permission assignment edges with $?$ abstract state,
shown as the graph (D). Last, a permission assignment edge is sampled from the
probability distribution, which is converted into a query with the same
corresponding entity and permission, as the output of the query model. For
example, as shown in Figure 7, the edge from Entity 4 to Perm 1 is sampled due
to its highest probability, thus the corresponding query $(\texttt{Entity
4},\texttt{Perm 1})$ is selected as the output.

Figure 8. The query model pretraining and selection.

####  4.3.3. Model Pretraining and Selection

As mentioned in Section 3.2.1, whether there is a permission flow from one
entity to anther depends on the entity types. Intuitively, a good query model
is able to distinguish privilege escalation tasks by the type of the
compromised entity, as different compromised entity types may have TAC to make
different queries for exploiting different permission flows during the
privilege escalation detection. Furthermore, for IAM configurations with the
same compromised entity type, the optimal query policies may be similar.

Based on the above intuitions, for each compromised entity type, we pretrain
one query model on all pretraining tasks with the same type. Figure 8 presents
the pretraining and selection of our query models. Given a pretraining task
set, we first classify it into groups based on the compromised entity type.
For each group, we pretrain a query model using RL with multiple episodes on
each task in the group. For example, consider Group 1 containing $m$ tasks. A
query model Model 0 is randomly initialized with the deep learning platform
(e.g., pytorch). Model 0 is trained on Task 1 and becomes a new query model
Model 1, which is then trained on Task 2 and becomes a new query model Model
2. The iterations continues until Model m-1 is trained on Task m and becomes
the pretrained query model for Group 1. Given a new task, a pretrained query
model is selected based on the compromised entity type of the task and then
used to initialize the query model for the new task.

###  4.4. Task Generator

Our pretraining approach requires the pretraining tasks to have enough tasks
with diverse compromised entity types. To the best of our knowledge, there is
only one publicly available IAM privilege escalation task set called IAM
Vulnerable (Art, 2021a), containing 31 tasks with only two compromised entity
types, which obviously does not meet the requirement. Regarding this, we
propose our own task generator called IAMVulGen.

Task Set | Source | # Task | # Compromised | # Visible Entity | # Visible Perm Flow | # Permission
---|---|---|---|---|---|---
Entity Type | min | max | avg | min | max | avg | min | max | avg
Pretrain | IAMVulGen | 500 | 68 | 2 | 27 | 14 | 2 | 235 | 66 | 6 | 260 | 78
Test-A | IAMVulGen | 500 | 68 | 3 | 27 | 14 | 2 | 300 | 70 | 12 | 322 | 72
Test-B | IAM Vulnerable | 31 | 2 | 1 | 3 | 2 | 0 | 6 | 2 | 3 | 12 | 7
Table 1. Statistics of three privilege escalation task sets. Detector | False Negative Rate
---|---
$\mathtt{QB}=200$ | $\mathtt{QB}=400$ | $\mathtt{QB}=600$ | $\mathtt{QB}=800$ | $\mathtt{QB}=1,000$ | $\mathtt{QB}=1,200$ | $\mathtt{QB}=1,400$
Q-Pacu | $0.898$ | $0.898$ | $0.898$ | $0.898$ | $0.898$ | $0.898$ | $0.898$
Q-Cloud | $0.902$ | $0.902$ | $0.902$ | $0.902$ | $0.902$ | $0.902$ | $0.902$
Q-PMapper | $0.932\pm 0.002$ | $0.926\pm 0.002$ | $0.924\pm 0.002$ | $0.923\pm 0.001$ | $0.922\pm 0.001$ | $0.922\pm 0.001$ | $0.922\pm 0.001$
TAC-RD | $0.676\pm 0.016$ | $0.450\pm 0.013$ | $0.315\pm 0.015$ | $0.226\pm 0.008$ | $0.168\pm 0.007$ | $0.124\pm 0.007$ | $0.095\pm 0.006$
TAC-EA | $0.666\pm 0.011$ | $0.436\pm 0.012$ | $0.314\pm 0.013$ | $0.225\pm 0.012$ | $0.165\pm 0.010$ | $0.121\pm 0.006$ | $0.094\pm 0.009$
TAC-NoPT | $0.673\pm 0.014$ | $0.444\pm 0.015$ | $0.313\pm 0.014$ | $0.233\pm 0.015$ | $0.172\pm 0.017$ | $0.126\pm 0.012$ | $0.096\pm 0.010$
TAC | $\mathbf{0.639\pm 0.007}$ | $\mathbf{0.423\pm 0.010}$ | $\mathbf{0.298\pm 0.017}$ | $\mathbf{0.220\pm 0.015}$ | $\mathbf{0.163\pm 0.009}$ | $\mathbf{0.118\pm 0.012}$ | $\mathbf{0.089\pm 0.009}$
Table 2. False negative rates of TAC and six baselines on the Test-A.

IAMVulGen randomly generates IAM privilege escalation tasks from a large
entity and permission space with all kinds of entity and permission types
manually identified based on AWS official documentation (AWS, 2023c, f, b) and
studies on IAM privilege escalations (Gietzen, 2018; Kleijn, 2022; Kedrosky,
2022; Xscaler, 2021). Each task includes a concrete IAM configuration only
accessible to the query oracle for generating query results, and the
corresponding initial abstract IAM configuration as the input of TAC. Each
task is generated in the following five steps.
Step 1: a PFG $G=(E,F,\mathcal{A},\mathcal{W})$ is created with four
components:
_(1) Entity Space $E$:_ We manually identify 72 common entity types from AWS
official service documentations (AWS, 2023c, f, b), including user, user
group, role, and 69 service types. $n$ ($n\in[1,5]$ by default) entity types
is uniformly sampled from identified entity types. For each sampled type, $m$
($m\in[1,20]$ by default) entities are generated.
_(2) Permission Flow Space $F$:_ We generate permission flows based on 219
_permission flow templates_ manually extracted from AWS service authorization
reference documentation (AWS, 2023c) and studies on IAM privilege escalations
(Gietzen, 2018; Kleijn, 2022; Kedrosky, 2022; Xscaler, 2021). The template
identifies the type of each entity pair that has a permission flow. Given the
generated entity space $E$, we add a permission flow between each entity pair
that has the identified type in a template.
_(3) Permission Assignment $\mathcal{A}$:_ We first need to generate a
permission space $P$ including Type-I, Type-II, and target permissions. One
Type-I permission is added for each generated permission flow to enable the
flow. For Type-II permission, we manually identify three entity types (i.e.,
user, user group and role) which can be directly assigned with a Type-I/target
permission; for each entity with one of these types and each Type-I/target
permission, we generate a Type-II permission for assigning the Type-I/target
permission to the entity. For target permission, based on AWS IAM security
best practice documentation (AWS, 2023f) and studies (Gietzen, 2018; Kleijn,
2022; Kedrosky, 2022; Xscaler, 2021), we manually identify permissions which
attackers usually target to obtain (e.g., the permission to access a sensitive
S3 bucket). With the generated permission space, we create the permission
assignments $\mathcal{A}$. Each entity are assigned with $\gamma_{p}$
($\gamma_{p}=20\%$ by default) of permissions uniformly sampled from the
permission space.
_(4) Flow State Function $\mathcal{W}$:_ For each permission flow, we set its
state to true with the probability of $\gamma_{w}$ ($\gamma_{w}=0.2$ by
default) and to false with the probability of $1-\gamma_{w}$.
Step 2: the fixed point iteration is performed on the generated PFG to get a
concrete IAM configuration, as introduced in Section 3.2.1.
Step 3: an entity is uniformly sampled from the entity space (except user
group) as the compromised entity, and a permission is uniformly sampled from
the permission space as the target permission.
Step 4: check if there is a privilege escalation in the concrete IAM
configuration, as introduced in Section 3.2.4. If so, the process continues to
step 5; otherwise, the process starts over from step 1.
Step 5: $\gamma_{v}$ ($\gamma_{v}=20\%$ by default) of entities in the
concrete IAM configuration is uniformly sampled as the visible entities, with
which an initial abstract IAM configuration is created, as introduced in
Section 3.3.1. The initial abstract IAM configuration and the concrete IAM
configuration constitutes a new task.

##  5\. Evaluation

###  5.1. Experimental Setup

####  5.1.1. Pretraining and Testing Task Sets

To pretrain and evaluate TAC, we construct the pretraining and testing task
sets based on our task generator IAMVulGen and the only publicly available IAM
privilege escalation task set (that we are aware of) IAMVulnerable (Art,
2021a). For the pretraining task set called Pretrain, we apply IAMVulGen with
its default setting to randomly generate $500$ IAM privilege escalation tasks.
Besides, we create two testing task sets: 1) Test-A set consisting of 500 new
tasks randomly generated by IAMVulGen under its default setting, and 2) Test-B
set consisting of 31 privilege escalation tasks in IAM Vulnerable (by adding
the corresponding initial abstract IAM configurations using our abstract
modeling).

Table 1 shows the statistics of the generated task sets. The Pretrain task set
includes diverse privilege escalation tasks with 68 compromised entity types,
having $2$–$27$ visible entities, $2$–$235$ visible permission flows, and
$6$–$260$ permissions. The Test-A task set has similar statistics. In
contrast, Task-B set includes much smaller and fewer diverse tasks with only
$2$ compromised entity types, $1$–$3$ visible entities, $0$–$6$ permission
flows, and $3$–$12$ permissions.

####  5.1.2. Local Query Oracle Simulation

As introduced in Section 3.3.4, our query-based IAM testing requires a query
oracle to provide query results. One straightforward way is to configure the
official IAM policy simulator (AWS, 2023g) as the query oracle by setting up
an experimental cloud organization on a real cloud platform (i.e., AWS) with
the privilege escalation tasks deployed. However, for our experiments, this
setting would incur substantial financial expenses. Because the IAM policy
simulator requires that all entities and resources involved in a query must
truly exist in the AWS organization. Creating all real entities for each
concrete IAM configuration in our experiments is prohibitive. Regarding this,
we build a _local_ query oracle simulator based on the Gymnasium software
package (Foundation, 2023), which has been widely used to construct simulated
RL environments. Given a concrete IAM configuration and a query about the
permission assignment information as inputs, our local simulator responses to
the query w.r.t. the concrete IAM configuration.

####  5.1.3. Baselines

Since there is no publicly available greybox or blackbox IAM privilege
escalation detector, we adapt three state-of-the-art whitebox detectors into
three greybox detectors as our baselines. In addition, to evaluate how our RL
approach contributes, we build three variants of TAC with different query
models.

We notice that there are two whitebox detectors called Pacu (Lab, 2022) and
Cloudsplaining (Salesforce, 2022) which only rely on the complete IAM
configuration to check whether the compromised entity has any permissions in a
sensitive permission list (manually identified by cloud security experts).
Based on this observation, we adapt Pacu and Cloudsplaining into two greybox
detectors Q-Pacu and Q-Cloud respectively, which send queries to our query
oracle to check whether the compromised entity has sensitive permissions,
instead of checking the complete IAM configurations. In addition, as
introduced in Section 2, PMapper relies on the complete IAM configuration to
have the permission assignment information (of users/roles) to do the graph
modeling. Regarding this, we adapt PMapper into a greybox detector called
Q-PMapper, which sends queries to obtain such information.

To understand how RL helps to improve the performance of the query model, we
build two variants of TAC: one with a query model which randomly selects
queries, namely TAC-RD, and the other one with a query model trained by the
state-of-the-art evolutionary algorithm called CMA-ES (Hansen, 2006), namely
TAC-EA. To understand how pretraining helps to improve the query model
performance, we build another variant of TAC having the query model
initialized with default model parameters by pytorch without pretraining,
namely TAC-NoPT.

####  5.1.4. Evaluation Metrics

We use two metrics to evaluate a greybox detector: False Negative Rate
($\mathtt{FNR}$) and Average Query Rate ($\mathtt{AQR}$). Formally, let $T$ be
the task set, $|T|$ refers to the size of the task set $T$, let $D\subseteq T$
be privilege escalation tasks that are successfully identified by the
detector, and $|D|$ be the size of the task set $D$. The $\mathtt{FNR}$ is
used to measure the soundness of a detector, which is defined as
$\mathtt{FNR}=\frac{|T|-|D|}{|T|}$. Note that we do not measure false positive
rates, as all detectors in our experiments are _precise_. We use
$\mathtt{AQR}$ to measure the query efficiency, defined as
$\mathtt{AQR}=\frac{1}{|D|}\sum_{d\in D}\frac{s_{d}}{q_{d}}$, where, for each
task $d$, $s_{d}$ refers to the number of queries sent and $q_{d}$ refers to
the size of the query space (defined in Section 3.3.4).

####  5.1.5. Query Budget Settings

In our evaluation, we evaluate the detectors with various query budgets. For
Pretrain task set, each task is pretrained within a query budget of its query
space size. The idea is to let the query model make enough explorations and
learn how to make query decisions with diverse kinds of states. For Test-A
task set, each task is tested within seven different query budgets: $200$,
$400$, $600$, $800$, $1,000$, $1,200$ and $1,400$. Note that the query budgets
are set much smaller than the maximum size of the query space which is
$6,615$. The goal is to observe how the detectors perform under relatively
small query budgets. For Test-B task set (the maximum size of the query space
is $27$), the query budgets are set to $10$ and $20$ respectively.

####  5.1.6. Hyper-Parameters Settings

In the pretraining, each task is used to pretrain a query model in 20
episodes. To obtain reliable estimates of the metrics, both the pretraining
and testing are repeated 11 times. In addition, the Adam optimizer (Kingma and
Ba, 2014) with a learning rate of $10^{-4}$ is applied in both the pretraining
and testing.

Figure 9. The average query rate of TAC and its three variants on Test-A with
seven query budgets. The error bars denote the standard deviations of average
query rates in 11 experiment repeats.

###  5.2. Research Questions

We try to answer three research questions in our experiments:
RQ1: How does TAC perform on Test-A in the false negative rate?
RQ2: How does TAC perform on Test-A in the average query rate?
RQ3: How does TAC perform on the publicly available Test-B?

###  5.3. Experimental Results

####  5.3.1. RQ1: False Negatives

Table 2 shows the false negative rates of TAC and six baselines on Test-A set.
About 90%-93% privilege escalation tasks cannot be detected by Q-Pacu, Q-Cloud
and Q-PMapper. Note that the false negative rates of Q-Pacu and Q-Cloud have
zero standard deviation and stay unchanged with different query budgets,
because they deterministically send much fewer queries than the query budgets
based on their manually identified sensitive permission lists (Q-Pacu and
Q-Cloud send 41 and 35 queries on average in detecting each task,
respectively).

In contrast, TAC and its three variants detect 22%-83% more privilege
escalation tasks than Q-Pacu, Q-Cloud and Q-PMapper, with less than 2%
standard deviations. In addition, TAC has the lowest false negative rates
across all seven query budgets. As the query budget increases from $200$ to
$1,400$, the false negative rate of TAC decreases significantly from $64\%$ to
$9\%$. _In general, results show that TAC is able to detect IAM privilege
escalation tasks on Test-A set with lower false-negative rates than the
baselines._

####  5.3.2. RQ2: Query Efficiency

With the low false negative rates of TAC and its variants on Test-A set, we
further compare TAC with its variants in terms of the average query rate, to
see how our proposed RL with pretraining helps to improve the query
efficiency. As shown in Figure 9, TAC always detects with the lowest average
query rate across all seven query budgets. In addition, compared to TAC, TAC-
EA consumes $5\%$–$8\%$ more queries; TAC-NoPT consumes $6\%$–$9\%$ more
queries; TAC-RD consumes $7\%$–$10\%$ more queries. In addition, for TAC, the
standard deviation of the average query rate is only $0.6\%$–$1.3\%$, while
for TAC-EA, the standard deviation is $0.8\%$–$1.7\%$; for TAC-RD, is
$1.1\%$–$1.8\%$; for TAC-NoPT, is $1.2\%$–$2.3\%$. Therefore, we can say that
TAC has stable performance in query efficiency. More importantly, we can
observe a large gap between TAC and the three variants, which shows the
superiority of TAC in query efficiency. _In conclusion, comparing TAC with
TAC-EA and TAC-RD, results show that our RL approach helps a lot in increasing
the query efficiency; comparing TAC with TAC-NoPT, results show that
pretraining is essential for improving the query efficiency._

####  5.3.3. RQ3: Performance on Public Task Set

Results on Test-B show that, Q-Pacu detects 11 privilege escalation tasks (FNR
is $0.645$); Q-Cloud detects 15 ($\mathtt{FNR}$ is $0.516$); Q-PMapper detects
6 ($\mathtt{FNR}$ is $0.806$); TAC’s variants detect 17-22 under the query
budget of 10 ($\mathtt{FNR}$ is $0.290$-$0.451$), and detect 23-30 under the
query budget of 20 ($\mathtt{FNR}$ is $0.032$-$0.258$). In contrast, TAC
detects 23 tasks under the query budget of 10 ($\mathtt{FNR}$ is $0.258$), and
detects all 31 tasks under the query budget of 20 ($\mathtt{FNR}$ is $0$). For
each detected task, Q-Pacu and Q-Cloud send 3 queries on average, and
Q-PMapper sends 6; TAC and its variants send 5 under the query budget of 10,
and 7-8 under the query budget of 20. _Overall, TAC achieves lowest false
negative rate with good query efficiency on Test-B task set_.

##  6\. Conclusion

In this paper, we proposed the first greybox penetration testing approach
called TAC for third-party cloud security services to detect IAM privilege
escalations due to misconfigurations. Unlike the whitebox approaches requiring
cloud customers to provide their complete IAM configurations, TAC allows cloud
customers to 1) specify which entities in their IAM configuration can be
queried for the permission assignment information, and 2) limit the maximum
amount of queries. TAC relies on our abstract IAM modeling to identify IAM
privilege escalation on partial IAM configuration, and GNN-based RL approach
with pretraining to learn to accomplish the detection within the query budget.
To pretrain and evaluate TAC, we proposed an IAM privilege escalation task
generator called IAMVulGen. Experimental results show that TAC is a promising
approach which detects IAM privilege escalations with significantly low false
negative rates and high query efficiency.

## References

  * (1)
  * Alliance (2021) Cloud Security Alliance. 2021\.  Roles and Responsibilities of Third Party Security Services.  https://cloudsecurityalliance.org/artifacts/roles-and-responsibilities-of-third-party-security-services/.
  * Art (2021a) Seth Art. 2021a.  IAM Vulnerable - An AWS IAM Privilege Escalation Playground.  https://bishopfox.com/blog/aws-iam-privilege-escalation-playground.
  * Art (2021b) Seth Art. 2021b.  IAM Vulnerable - Assessing the AWS Assessment Tools.  https://bishopfox.com/blog/assessing-the-aws-assessment-tools.
  * AWS (2023a) AWS. 2023a.  AWS IAM API Reference: SetDefaultPolicyVersion.  https://docs.aws.amazon.com/IAM/latest/APIReference/API_SetDefaultPolicyVersion.html.
  * AWS (2023b) AWS. 2023b.  AWS Identity and Access Management (IAM).  https://aws.amazon.com/iam/.
  * AWS (2023c) AWS. 2023c.  AWS Service Authorization Reference: Actions, resources, and condition keys for AWS services.  https://docs.aws.amazon.com/pdfs/service-authorization/latest/reference/service-authorization.pdf#reference_policies_actions-resources-contextkeys.
  * AWS (2023d) AWS. 2023d.  How AWS Verified Access works with IAM.  https://docs.aws.amazon.com/verified-access/latest/ug/security_iam_service-with-iam.html.
  * AWS (2023e) AWS. 2023e.  Penetration Testing.  https://aws.amazon.com/security/penetration-testing/.
  * AWS (2023f) AWS. 2023f.  Security best practices in IAM.  https://docs.aws.amazon.com/IAM/latest/UserGuide/best-practices.html.
  * AWS (2023g) AWS. 2023g.  Testing IAM policies with the IAM policy simulator.  https://docs.aws.amazon.com/IAM/latest/UserGuide/access_policies_testing-policies.html.
  * AWS (2023h) AWS. 2023h.  Using AWS IAM Access Analyzer.  https://docs.aws.amazon.com/IAM/latest/UserGuide/what-is-access-analyzer.html.
  * Backes et al. (2018) John Backes, Pauline Bolignano, Byron Cook, Catherine Dodge, Andrew Gacek, Kasper Luckow, Neha Rungta, Oksana Tkachuk, and Carsten Varming. 2018.  Semantic-based automated reasoning for AWS access policies using SMT. In _2018 Formal Methods in Computer Aided Design (FMCAD)_. IEEE, 1–9.
  * Bouchet et al. (2020) Malik Bouchet, Byron Cook, Bryant Cutler, Anna Druzkina, Andrew Gacek, Liana Hadarean, Ranjit Jhala, Brad Marshall, Dan Peebles, Neha Rungta, et al. 2020\.  Block public access: trust safety verification of access control policies. In _Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 281–291.
  * Brody et al. (2021) Shaked Brody, Uri Alon, and Eran Yahav. 2021.  How attentive are graph attention networks?  _arXiv preprint arXiv:2105.14491_ (2021).
  * Cybersecurity Insiders (2021) Cybersecurity Insiders. 2021\.  Cloud Security Report.  https://www.isc2.org/Landing/cloud-security-report.
  * DivvyCloud (2020) DivvyCloud. 2020\.  2020 Cloud Misconfigurations Report.  https://divvycloud.com/wp-content/uploads/2020/02/Cloud-Misconfiguration-Report-FINAL.pdf.
  * Foundation (2023) The Farama Foundation. 2023\.  Gymnasium Documentation.  https://gymnasium.farama.org/.
  * Gietzen (2018) Spencer Gietzen. 2018\.  AWS IAM Privilege Escalation – Methods and Mitigation.  https://rhinosecuritylabs.com/aws/aws-privilege-escalation-methods-mitigation/.
  * Group (2023) NCC Group. 2023\.  Principal Mapper.  https://github.com/nccgroup/PMapper.
  * Hansen (2006) Nikolaus Hansen. 2006\.  The CMA evolution strategy: a comparing review.  _Towards a new evolutionary computation_ (2006), 75–102.
  * Kedrosky (2022) Eric Kedrosky. 2022\.  Achieving AWS Least Privilege: Understanding Privilege Escalation.  https://sonraisecurity.com/blog/common-methods-aws-privilege-escalation/.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Kleijn (2022) Gerben Kleijn. 2022\.  Well, That Escalated Quickly: Privilege Escalation in AWS.  https://bishopfox.com/blog/privilege-escalation-in-aws.
  * Lab (2022) Rhino Security Lab. 2022\.  Pacu: The Open Source AWS Exploitation Framework.  https://rhinosecuritylabs.com/aws/pacu-open-source-aws-exploitation-framework/.
  * Labs (2022) WithSecure Labs. 2022\.  A graph-based tool for visualizing effective access and resource relationships in AWS environments.  https://github.com/WithSecureLabs/awspx.
  * Morag (2021) Assaf Morag. 2021\.  Cloud Misconfigurations: The Hidden but Preventable Threat to Cloud Data.  https://www.infosecurity-magazine.com/opinions/cloud-misconfigurations-threat/.
  * One (2022) Capital One. 2022\.  Information on the Capital One Cyber Incident.  https://www.capitalone.com/digital/facts2019/.
  * Pernetf (2021) Cedric Pernetf. 2021\.  Research reveals that IAM is too often permissive and misconfigured.  https://www.techrepublic.com/article/research-iam-permissive-misconfigured/.
  * Quist (2021) Nathaniel Quist. 2021\.  Unit 42 Cloud Threat Report Update: Cloud Security Weakens as More Organizations Fail to Secure IAM.  https://unit42.paloaltonetworks.com/iam-misconfigurations/.
  * Rungta (2022) Neha Rungta. 2022\.  A billion SMT queries a day. In _Computer Aided Verification: 34th International Conference, CAV 2022, Haifa, Israel, August 7–10, 2022, Proceedings, Part I_. Springer, 3–18.
  * Salesforce (2022) Salesforce. 2022\.  Cloudsplaining.  https://cloudsplaining.readthedocs.io/en/latest/.
  * Sehgal (2021) Hemani Sehgal. 2021\.  Cloud Security Conundrum Debunked: Native Vs. Third-Party Tools.  https://www.horangi.com/blog/cloud-security-native-third-party-tools.
  * Sutton and Barto (2020) Richard S Sutton and Andrew G Barto. 2020.  _Reinforcement learning: An introduction_.  MIT press.
  * Xscaler (2021) Xscaler. 2021.  Anatomy of a Cloud Breach: How 100 Million Credit Card Numbers Were Exposed.  https://www.zscaler.com/resources/white-papers/capital-one-data-breach.pdf.