# Performance Analysis of the Hybrid IoT Security Model of MQTT and UMA

Khalid S. Aloufi
Department of Computer Engineering
Taibah University
Medina
<EMAIL_ADDRESS>
& Omar H. Alhazmi
Department of Computer Science
Taibah University
Medina
<EMAIL_ADDRESS>
Use footnote for providing further information about author (webpage,
alternative address)— _not_ for acknowledging funding agencies.

###### Abstract

IoT applications are promising for future daily activities; therefore, the
number of IoT connected devices is expected to reach billions in the coming
few years. However, IoT has different application frameworks. Furthermore, IoT
applications require higher security standards. In this work, an IoT
application framework is presented with a security embedded structure using
the integration between message queue telemetry transport (MQTT) and user
managed access (UMA). The performance analysis of the model is presented.
Comparing the model with existing models and different design structures shows
that the model presented in this work is promising for a functioning IoT
design model with security. The security in the model is a built-in feature in
its structure. The model is built on recommended frameworks; therefore, it is
ready for integration with other web standards for data sharing, which will
help in making IoT application integrated from different developing parties.

_K_ eywords IoT $\cdot$ MQTT $\cdot$ UMA $\cdot$ Network Security $\cdot$
Smart City

##  1 Introduction

Over the past few years, one of the remarkable emerging technologies is the
Internet of Things (IoT). It has vast varieties of possible applications, with
a wide range of requirements in terms of security and performance. Several
networking protocols are designed with performance in mind, then security is
added later. Thus, security is often considered a burden and an overhead to
the original protocol. The original non-secure protocol requires less
communication and encryption overhead. Moreover, an IoT environment mainly
consists of constrained devices, with limited resources and capabilities,
which makes performance vital for the environment. There is an essential need
for a protocol that distributes the load and decentralizes security in order
to have a scaleable IoT environment and satisfy the performance and security
requirements at the same time. One of the widely accepted IoT protocol is
Message Queuing Telemetry Transport (MQTT). MQTT is an ISO standard (ISO/IEC
PRF 20922)[1]. It is a lightweight, publish-subscribe network protocol that
transports messages between devices. MQTT typically runs over TCP/IP. It is
designed for connections with remote locations where a "small code footprint"
is required or the network bandwidth is limited. MQTT does not provide
security by itself. Therefore, there have been some improvements to MQTT to
improve its security; however, the overhead remains a critical issue in an
environment with constrained devices.

On the other hand, User Managed Access(UMA) provides security. User-Managed
Access (UMA) is an OAuth-based access management protocol standard. Version
1.0 of the standard was approved by the Kantara Initiative on March 23,
2015.[2] OAuth is an open standard for access delegation, commonly used as a
way for Internet users and applications to grant websites or applications
access to their information on other websites. It leaves the power with the
owner to control authorization. It provides privacy and consent implications
for web applications and the Internet of Things (IoT).

In the rest of this paper, we present some related work, then the background
of MQTT and UMA; next, we propose a hybrid model by mapping MQTT and UMA. By
simulation we evaluate the proposed secure MQTT/UMA hybrid system. Then the
simulation experiment results is presented, discussed and analyzed; finally, a
conclusion and final remarks are summarized and some future research
directions are presented.

##  2 Related Work

Internet of Things deployment remains a major challenge; hence, many have
suggested using the cloud as a platform for the Internet of Things [3]. It has
also been suggested that IoT sensors can be integrated into the cloud [4];
moreover, the business model can be built around providing Sensing as a
Service module (SenaaS) [5]

Neven Nikolov and Ognyan Nakov have suggested using MQTTS and SSL/SSH
encryption for IoT devices[6]. Such a scheme can be effective; however, the
performance impact on IoT should be carefully investigated. Others have also
proposed some amendments to MQTT by using Attribute Based Encryption (ABE) to
secure some aspects of MQTT[7][8].

Perira et al. have listed challenges of IoT, which are automated sensor
configuration and context discovery context acquisition, modeling, reasoning,
and distribution selection of sensors in sensing-as-a-service (SenaaS) models
security, and privacy-trust and context sharing[9].

Dai, Zheng and Zhang have proposed Block Chain of Things (BCoT) to secure IoT
devices. Their model, seems very secure. However, the high demand for
resources can make it infeasible with the current constrained IoT devices.
[10]

Niruntasukrat et al. have modified the OAuth 1.0a framework to accommodate the
restrictions of IoT devices.[11]

Ullah, Ahmed and Kim have proposed information-centric networking [12]. They
have elaborated on the importance of the fog layer, as a practical and gap
filler layer in any deployment of the IoT/Cloud environment.

Aloufi and Alhazmi have shown how deploying IoT devices using fog computing
has evident performance advantages [13]. Moreover, in [14] they have suggested
an IoT implementation by mapping MQTT protocols over the cloud-fog by placing
the broker on the fog; the results show that the proposed scheme improves
performance and reliability.

Cruz-Piris et al. have proposed access control mechanism for IoT using Oauth
2.0 with MQTT[15].

##  3 Background

###  3.1 MQTT

There are different IoT protocols, such as MQTT and CoAP. While CoAP is highly
competitive with MQTT. CoAP has a mechanism of exploration and observation;
however, MQTT is much simpler to implement and much more popular [16][17][18].
As shown in figure 2, MQTT consists of clients and a broker. The main unit is
the broker, which manages messages and transactions between clients. Clients
are either a subscriber or a publisher. The payload of messages transmitted
between clients contains data, mainly a subject and its value. The publisher
sends messages to the broker when it has an update message or a periodic
message. The broker sends the messages to the subscribers of a specific
subject. Figure 1 shows that MQTT transaction.

$C_{P}$(Publishers) MQTT $C_{S}$(Subscribers) $Connect$$ConnectionACK$$publish(Topic,value)$$publish(Topic,value)$$Connect$$ConnectionACK$$subscribe(Topic,value)$ Figure 1: MQTT publish and subscribe Transactions MQTT Client MQTT Client MQTT Broker MQTT Client MQTT Client MQTT Client MQTT Client ⋮⋮subscribesubscribesubscribemessagemessagemessagepublishpublishpublish Figure 2: MQTT Table 1: Internet Of Things Stack Layer | OSI Layers | TCP/IP | IoT
---|---|---|---
7 | Application | Application | MQTT
6 | Presentation
5 | Session
4 | Transport | Transport | TCP
3 | Network | Internet | IP
2 | Data Link | Network Access | IEEE 802.15.4 MAC
1 | Physical | IEEE 802.15.4 PYS

Table 1 shows the IoT stack model for MQTT. With correspondence of the TCP/IP
model, MQTT is one of the main IoT protocols because its messages are
transmitted over TCP connection, in contrast to some other protocols,such as
CoAP, which are transmitted over UDP. MQTT takes full advantage of the TCP/IP
model, making application development and understanding of the protocol
trivial. Also, MQTT integration over TCP help in the integration of MQTT with
other protocols that share the same stack.

###  3.2 UMA

OAuth2 is an open protocol to allow secure authorization of application
without providing the password[19]. User-Managed Access (UMA) is a profile of
OAuth 2.0. UMA defines how different entities communicates together. UMA
consists of resource owner(RO),resource server(RS), authorization server(AS),
client and the requesting party(RP). The components work together to provide
secure access to resources using protection API, authorization API and tokens
to access protected resource.

resource owner authorization server protectionAPI (needs PAT) authorization
API (needs AAT) client (requesting party) resource server protected resource
(needs RPT) control (c)authorize (D)protect (B)manage (A)access (E) Phase 1:
protect a resource Phases 2: get authorization Phases 3: get access a resource
Figure 3: The Three Phases of the UMA Profile of OAuth,[19].

The resource owner controls resource access by clients. The client is operated
by a requesting party. Resources are hosted by a resource server. An
authorization server has roles defined by the resource owner, to access
resources, . For example, a resource owner can grant access to an application
for one-time access to a resource following some roles defined by the owner
and managed by the authorization server.

There are three phases of the UMA of resources as shown in Figure 3, which are
protection, authorization and access[19]. The figure shows the transaction of
the three phases. In phase one, the resource owner is managing resources at
the resource server, ("A"). The resource owner controls the authorization
server,("C"), which provides the resources with protection API,(B). The
protection API require a protection API token (PAT) to access a resource. In
phase two, the authorization phase, the client gets access to a set of
resources in the resource server after being authorized by the authorization
server . The authorization API is using an authorization API token (AAT) to
get a requesting party token (RPT),("D"). Finally, in phase three, the client
accesses a resource in the resource server using an RPT, ("E").

Figure 4 shows the summarized transaction of the model. The client connects
with the RS. It gets the resource, then the client is connected with the AS to
get grant access and finally the client can get the resource from the RS. This
transaction is updated from the original one since the UMA model is updated
and the client has no direct connection with the RO [20].

The UMA model has different APIs and tokens to be used. Table 2 shows the list
of APIs used, tokens, the issuer and the user of the tokens. Using the
protection API, a Protection API Token(PAT) is issued by the AS to the RS to
access the protection API. The RS is then issued using the RPT to protect a
specific resource for a specific owner. An Authorization API Token(AAT) is
issued by the AS using the Authorization API when the RP contacts the AS with
a well-formatted request as recommended by UMA [19]. The RP will use the token
to contact the Authorization API again to get a Requesting Party Token (RPT),
which is the token that the RP is working to grant based on ATT.

Figure 5 shows the detailed UMA transaction [21, 22]. The RO logs in to the RS
to share a R. Then, the RS connects with the AS to get a PAT for the R. The AS
replies with a PAT with the R, RS and RO information. After that, when the
client (RP) requests access to the R at the RS, the client requires the access
credentials. For this reason, the client is communicating with the AS to get
the RPT and AAT for the specific R. Before the access permission, the AS set
the access permissions rules. Finally, the client gets the R with a valid RPT.
The UMA data should be exchanged in JSON format[21].

Table 2: UMA API and Tokens Token |  API |  Issued By |  Issed To |  To Access
---|---|---|---|---
Authorization Party Token (AAT) |  A API |  AS |  RP(Client) |  A API
protection API Token (PAT) |  P API |  AS |  RS |  P. API
Requesting Party Token (RPT) |  A API |  AS |  RP(Client) |  R in RS
Client Resource Owner Authorization Server Resource Server (A)- Authorization
Request(B)– Authorization Grant(C)-Authorization Grant(D)- Access Token (E)-
Access Token(F)- Protected Resource Figure 4: Summarized UMA Transactions
Client Resource Owner Resource Server Authorization Server Protection
Authorization Access logIn()/register(R,policy conditions)getPAT(R,policy
)(RO,RS,PAT)get(R)401+A. EndpointRegister
()AATgetRPT(AAT)RPTget(R,RPT)isValid(R,RPT)NosetPermission()Permission
Token403+PermissionTokengetRPT(AAT,PToken,iRPT)RPTgetR(RPT)isValid(R,RPT)YesR
Figure 5: Detailed UMA Transactions

##  4 MQTT/UMA Hybrid Model

The proposed model is a system composed of two known systems, which are the
UMA and MQTT. In the following sections, the model is developed. The first
step is to do a mapping between the functions of the MQTT and UMA protocols.
Then, in the next step, the model is proposed. The proposed model considers
both the functionality of MQTT and UMA to provide the features of both
protocols. Therefore, the model extends the area of application of UMA to
reach IoT devices that works with MQTT protocols. The model proposed should
increase the security level of small to large scale IoT application in smart
city or smart building applications.

###  4.1 UMA and MQTT Mapping

The model requires mapping between the functionality of both UMA and MQTT to
work as one system. This section shows the mapping of the function of both
protocols, UMA and MQTT. Table 3 shows the mapping required for the model
between MQTT and UMA to work effectively. UMA consists of authorization
server(AS),resource server(RS),resource owner(RO), client and requesting party
(RP). MQTT consists of MQTT broker,MQTT publisher and MQTT subscribers. The
AS,RS,RO, client and RP are mapped with the MQTT broker,MQTT publisher and
MQTT subscribers. The model, which will be detailed in section 4.2, consists
of one UMA and two MQTT. MQTT manages topics which is considered a R in UMA.

The first MQTT consists of MQTT Broker 1 (MB1), subscriber (S1) and publisher
(P1). The second MQTT consists of MQTT Broker 2 (MB1), subscriber (S2) and
publisher (P2). The model works by having P1 publish topics from IoT devices.
MB1 gets the published topics from P1. After-that, MB1 publishes topics to
MB2. S1 is MB2 and P2 is MB1. After the topic is published from P1 to MB1, MB2
gets the published topics from MB1. Finally, MB2 publishes topics to S2, the
subscriber in the second MQTT.

To add UMA to the model, MB1 is mapped with the RO because of the similar
functionality of both since both have resources to share. The S2 is mapped
with a RP since S2 subscribes to a topic with the MB2. The S2 is considered as
a RP because it will require use of a client to access a resource published by
a MB2. The MB2 works as a RS because of the similar functionality of holding
the resources access permissions. For the model to be practical and logical
for implementations, the AS and client are considered two different standalone
fog servers.

Table 3: Mapping UMA and MQTT  MQTT | UMA
---|---
P1 | non
MB1/P2 | RO
S1/MB2 | RS
non | AS
S2 | RP
non | Client
topic/subject | R

One of the main transactions added by the MQTT broker is the publishing of any
new topic value. Now the RS has the resource and has its value. The resource
is available for any successful RP access. However, when a new value of a
resource is received, RS has to update the resource and publish the resource
to its subscribers. The integration between the functionality of the MB2 and
RS is the main addition of the model.

###  4.2 The Model

Figure 6 shows the applicable network model proposed in this work. The model
consists of the P1 as a publisher, S2/RP as a subscriber, RS/MB2/S1,
MB1/P2/RO, client and AS. As will be shown later, most of the transaction
messages of the proposed model are between the three main entities, which are
S1/MB2/RS, client and AS. Therefore, to increase the performance of the model,
RS/MB2/S1, Client and AS are located in the fog layer.

As known and shown earlier in section 3.1, the basic MQTT model consists of a
MQTT broker, subscribers and publishers. In the model two MQTT models are
joined to make a new MQTT model. Technically there are no P2 and S1 in the
system. P2 and S1 functionality are integrated in MB1 and MB2, consequently.

S2/RP gets the messages from the fog layer, which is expected to provide more
connectivity in availability and connection speed compared to the first mode
as well as more security enhancement with UMA model. MB2 is located in the fog
layer, which is connected directly with MB1.

The model can be extended by having the MB2 connected to more than one MB1.
Furthermore, each MB1 could be using one or more methods for connectivity to
the fog layer. The fog layer provides more performance and security of the
high Quality of Service (QoS) required of a large-scale application [23]. One
of the expected benefits of using the fog cloud is to decrease the response
time between the subscribers and publishers. The publishers notify the broker
for any updates and the broker notifies the subscribers. The broker also has
the log of each publisher in case it is needed by subscribers or for more
statistical computations, such as the average value of a specific publisher or
timing values, such as the last time a specific publisher updated its value.

Fog LayerP1P1P1Internet MB1/P2/RO AS S1/MB2/RS S2/RP Client Figure 6: System
Model

##  5 Model Evaluation

In this section, we describe the evaluation methodology, which consists of
four parts: the simulation setup, the simulation presentation; the results and
discussion are presented afterward.

###  5.1 System Initial Configuration

This section shows the results and discussion of the simulation experiments of
the IoT model shown earlier in section 4.2. As shown in figure 7, the model
contains P1, MB1/P2/RO, S1/MB2/RS, client, S2/RP and AS.

While P1 is in direct connection to MB1/P2/RO, there is no direct connection
between MB1/P2/RO and S2/RP.S2/RP gets the published topic from S1/MB2/RS,
which is well established in security and performance in the fog layer.
MB1/P2/RO is expected to be a private property node in a home or a building at
a security level that should not establish connection with general
connections, such as RPs. Also, S1/MB2/RS is assumed to be connected with
MB1/P2/RO with normal Internet connection.

This is an increase in security without added security overhead for MB1/ P2/RO
messages. Effectively, the gained security overhead for messages is added to
messages between S1/MB2/RS and MB1/P2/RO and between S1/MB2/RS and S2/RP.

In section 3.2, Figure 5 shows the detailed UMA transactions to add security
for general systems. Figure 7 shows messages exchange between UMA and MQTT
units to provide a reliable IoT system that uses UMA as an added security
layer. Most messages transactions in the model are between the RS, client and
AS. Therefore, S1/MB2/RS , AS and client are allocated in the model in the fog
layer with high speed connection with each other to increase QoS.

S2/RP/Client MB1/P2/RO P1 S1/MB2/RS AS Protection / Publish Authorization /
Subscribe Transactions, Detailed in Figure 5 Access / Publish
subscribe(R)publish(Rpublish(RConnectConnectAckpublish(R)publish(R)getPAT(R)(RO,RS,PAT)publish(R)publish(R)Access(R,RPT)isValid(R,RPT)Yes
Figure 7: MQTT UMA Subscribe Transactions

###  5.2 Evaluating the Model

The model evaluation is done through simulation of the MQTT/UMA hybrid system.
To configure the simulation model, the system is configured as follows. The
wireless connection with any entity in the fog layer is 120 Mbps, assumed by a
ping to the MQTT broker at test.mosquitto.org, and also tested by Jaloudi
[24]. MB1/P2/RO can get from 10-100 Mbps over 802.11g protocol or wired
connection. Therefore, MB1/P2/RO can connect with several IoT devices at once,
with a high data rate from IoT. However, the sending rate of each IoT device
is much lower, allowing the broker to receive data from several IoT devices.
Each IoT device is equipped with Zigbee, using an IEEE 802.15.4 antenna, with
a rate of 250 kbps and the maximum message size is 127 bytes, according to the
Zigbee Specification [25]. As a result, the transmission time of one message
is about 4 ms.

Fog servers are assumed to be equipped with powerful nodes, such as Intel Xeon
W-3275M @ 2.50GHz. In the fog server, the mean time required to access a
database at the S1/MB1/RS is 13 ms The mean time required to query the
database is about 10 ms. The mean processing time at the S1/MB2/RS, AS, and
client is 10 ms. IoT devices represented by $P1$ are publishing data with the
Poisson arrival process.

A ping between two servers in Europe, assumed to be servers in the fog layer,
requires between 3 ms and 100 ms, depending on the location of the fog
servers. In this work, it is assumed that the fog server is in the same area,
such as a country. Therefore, the assumed time is about 3 ms to exchange a
message between two fog servers. The tested ping between two fog servers in
different areas, like the US and Europe, is about 200 ms. From the simulation
experiments, the arrival rate of data from each of the IoT devices is 127
bytes per second, which is one reading of a subject data keeping the data size
minimal to avoid fragmentation.

Table 4: Processing and transaction required time Parameter |  $t$ (ms)
---|---
$T_{P1}$ | 10
$T_{MB1/P2/RO}$ | 100
$T_{AS}$ | 13 +10 +10
$T_{S1/MB2/RS}$ | 13 +10 +10
$T_{S2/RP}$ | 100
$T_{Client}$ | 10
$T_{P1xMB1/P2/RO}$ | 4
$T_{MB1/P2/ROxS1/MB2/RS}$ | 200
$T_{S1/MB2/RSxAS}$ | 3
$T_{ClientxS1/MB2/RS}$ | 3
$T_{ClientxAS}$ | 3
$T_{S2/RPxClient}$ | 200

Table 4 shows the transaction time between the different nodes of the model,
and the processing time at each node. The table is the conclusion of the
configuration of the model. The table is used to configure the simulation.
Processing time at the IoT device is defined by $T_{P1}$. The table symbols
are shown in Figure 8.

[step=300,max=1200,width=5.5cm] [label= Protection
Authorization,color=red!10]923 [label= Access,color=yellow]164 [label=Initial
Publish,color=red!30]1147 [label=Publish,color=blue!30]578 [label=Subscribe
,color=green!10]92 $ms$

Figure 8: Phases Processing Time
$1.56$$1.58$$1.6$$1.62$$1.64$$1.66$$1.68$$1.7$$\cdot
10^{-3}$$0.92$$0.94$$0.96$$0.98$$1$$\lambda$System Utilization Figure 9:
System Utilization

The transmission time between IoT device $P1$ and MQTT Broker $MB1/P2/RO$ is
defined by $T_{P1xMB1/P2/RO}$. The same applies to other transactions. The
symbols shown in the table are as follows. $P1$ is the IoT devices. $MB1$ is
the first broker connected directly with $P1$ and also connected with the $S1$
node. as the subscriber. $MB1$ shares the node with $P2$ and $RO$. The model
is mutually inclusive between the two-broker system of $MB1$ and $MB2$. $P2$
is the publisher of the second broker system. As mentioned, $P2$ share the
node with $MB1$ and $RO$. $MB2$ is the second broker and share the node with
$S1$ and $RS$. $MB2$ is connected with $S2$ through the $Client$. $S2$ shares
its node with $RP$.

$\displaystyle\begin{split}1xT_{MB1/P2/RO}+13xT_{AS}+\\\ 10xT_{S1/MB2/RS}+\\\
10xT_{Client}+\\\ 1xT_{MB1/P2/ROxS1/MB2/RS}+\\\ 6xT_{S1/MB2/RSxAS}+\\\
4xT_{ClientxS1/MB2/RS}+\\\ 6xT_{ClientxAS}&=1207ms\end{split}$ (1)

$\displaystyle\begin{split}2xT_{AS}+2xT_{S1/MB2/RS}+\\\ 2xT_{Client}+\\\
2xT_{S1/MB2/RSxAS}+\\\ 2xT_{ClientxS1/MB2/RS}&=164ms\end{split}$ (2)

$\displaystyle\begin{split}1xT_{P1}+3xT_{MB1/P2/RO}+\\\
2xT_{AS}+5xT_{S1/MB2/RS}+\\\ 3xT_{MB1/P2/ROxS1/MB2/RS}+\\\
2xT_{S1/MB2/RSxAS}&=1147ms\end{split}$ (3)

$\displaystyle\begin{split}1xT_{P1}+1xT_{MB1/P2/RO}+\\\ 2xT_{AS}+\\\
2xT_{S1/MB2/RS}+\\\ 1xT_{S2/RP}+\\\ 2xT_{Client}+1xT_{P1xMB1/P2/RO}+\\\
1xT_{MB1/P2/ROxS1/MB2/RS}+\\\ 2xT_{S1/MB2/RSxAS}+\\\ 2xT_{ClientxS1/MB2/RS}\\\
&=578ms\end{split}$ (4)

$\displaystyle\begin{split}2xT_{S1/MB2/RS}+\\\ 2xT_{Client}+\\\
2xT_{ClientxS1/MB2/RS}&=92ms\end{split}$ (5)

Equation 1 shows that 1207 $ms$ is required for protection and authorization,
. For initial access, Equation 2 shows that 164 $ms$ is required. Equation 3
shows the time of initial publishing is 1147 $ms$. For subsequent publishing,
the time required is 578 $ms$ as shown by Equation 4. In Figure 7, the
function $Access(R,RPT)$ is invoked only when the client initiates the
request; otherwise, the published message reaches to the $RP$ as a subscriber
to the subject. Equation 5 shows the subscriber transaction time is 92 $ms$.

$1.56$$1.58$$1.6$$1.62$$1.64$$1.66$$1.68$$1.7$$\cdot
10^{-3}$$0$$200$$400$$600$$\lambda$Mean waiting number Figure 10: Mean waiting
number $1.56$$1.58$$1.6$$1.62$$1.64$$1.66$$1.68$$1.7$$\cdot
10^{-3}$$0$$1$$2$$3$$\cdot 10^{5}$$\lambda$mean waiting time Figure 11: mean
waiting time $0$$100$$200$$300$$400$$500$$600$$0$$1$$2$$3$$\cdot 10^{5}$mean
waiting numbermean waiting time Figure 12: mean waiting time vs mean waiting
number $1.56$$1.58$$1.6$$1.62$$1.64$$1.66$$1.68$$1.7$$\cdot
10^{-3}$$0$$1$$2$$3$$\cdot 10^{5}$$\lambda$mean waiting time in the
system$1/587\mu$ Figure 13: Mean waiting time in the system
$1.56$$1.58$$1.6$$1.62$$1.64$$1.66$$1.68$$1.7$$\cdot
10^{-3}$$0$$200$$400$$600$$\lambda$mean number in the system$1/587\mu$ Figure
14: mean number in the system
$1.56$$1.58$$1.6$$1.62$$1.64$$1.66$$1.68$$1.7$$\cdot
10^{-3}$$0$$2$$4$$6$$8$$\cdot 10^{-2}$$\lambda$proportion of time the system
is idle$1/587\mu$ Figure 15: proportion of time the system is idle

##  6 Results and Discussion

###  6.1 Results

The system is M/M/1 queuing model with exponential distribution of inter
arrival time and service time. The system is tested with a mean inter-arrival
time between 588 ms and 640 ms. The mean service rate is $\mu=1/587$, which is
the time required for publishing.

The system utilization is computed by Equation 6 and shown in Figure 9. Mean
waiting number to be served is computed by Equation 7 and shown in Figure 10.
Mean waiting time is computed by Equation 8 and shown in figure 11. Mean
waiting number verses mean waiting time is shown by figure 12.

Mean waiting time in the system is computed by Equation 9 and shown in Figure
13. Mean waiting number in the system is computed by Equation 10 and shown in
Figure 14. Proportion of time the server is idle is computed by Equation 11
and shown in Figure 15.

$\rho=\lambda/\mu.$ (6)

$L_{q}=\frac{\rho^{2}}{1-\rho}$ (7)

$W_{q}=L_{q}/\lambda$ (8)

$W=W_{q}+1/\mu$ (9)

$L=\lambda W$ (10)

$idle\%=1-\rho$ (11)

###  6.2 Discussion

As the experiments in section 5.2 and the results in section 6.1 show, the
overhead created between UMA and MQTT is the main critical overhead by the
mode. The UMA and MQTT are originally separate models; each model with
different features and objectives. In the proposed model, MQTT and UMA are
integrated to provide extra layer for IoT devices of security. The main point
of adding UMA to MQTT or the vice versa is to add accessibility for users for
IoT devices. Any IoT device is not connected to the world unless connected to
a broker or a type of protocol, that allows the IoT device to send and receive
data. However, the accessibility of IoT devices is expected to be quite high;
therefore, UMA is provides high scaleability for IoT device to publish its
data to the wide range of users or $RP$. $RP$ could be another IoT device.
Nowadays with the expected future and developing project of smart cities and
buildings, IoT devices are expected to send very large amount of data as(i.e.
Big Data). Also, the integration of plug and play is a must future for IoT.
Now, UMA will establish protocols as well as MQTT. Adding the two models
should be done without sacrificing performance. If there is a trade-off, the
system administrator and project developer can discuss the QoS of any model of
expected growing IoT projects.

For MQTT, the model is added to UMA to add the subscriber functionality. The
model shown in Figure 6; has mainly $S1$ and$MB2$ added to the $RS$ and $S2$
added to $RP$. Effectively, $P1$, $MB1$ and $P2$ are not considered an
overhead, since it is external processing overhead to the UMA protocol.
Therefore, the overhead are with $S1$, $MB2$ and $S2$. When the data are
received from $P1$ to $MB1$, the data are published to $S1$. $S1$ is
represented by $MB2$, which is represented by $RS$. The integration between
$MB2$ and $RS$ is done by considering any newly published data received by
$MB2$ as a request received by a $RP$ which is registered as a subscriber for
a specific topic. Therefore, the time required to get a message about a new
topic is less than the time required for a request by $RP$ ,$Client$,
$S2/RP/xClient$$ClientxS1/MB2.RS/$and $S1/MB2/RS/$compared to the time
required for the publishing as mentioned earlier by Equation 4. The time
required is only 26% of the time required if the functionality is done by UMA
only. Consequently, the performance gain is 74& with MQTT for the publishing
function of a new topic.

##  7 Conclusion

In conclusion, IoT application are promising for future applications in
different domains, such as smart cities or the sensing as a service (SenaaS)
model of business. When an IoT application works it is expected that the
number of devices grows exponentially as well as the size of data. Security is
required to secure access to the data sources. Data needs to be protected
without compromising performance. Therefore, a security layer is required. In
this work, the UMA security protocol is used to add security with the well-
known IoT application protocol MQTT. There are different IoT application
protocols; however,MQTT is the most popular for implementations simplicity.
This work has shown how to integrate MQTT and UMA in one fast performance and
secure model. The integration is maintained by mapping the functionality of
both protocols. Performance comparison have shown that there is performance
gain for different functionality, mainly the publishing function. Publishing
is the main function of any IoT device. The model has successfully, connected
isolated IoT devices to the publishing network without compromising security.
The data are published and accessed without accessing the source of the data.
UMA is a promising model for IoT security,

## References

  * [1] ISO/IEC 20922:2016 MQTT v3.1.1.  https://www.iso.org/standard/69466.html.  Accessed: 2016-06-15.
  * [2] Kantara Initiative Staff.  User managed access, 2015.
  * [3] A. R. Biswas and R. Giaffreda.  Iot and cloud convergence: Opportunities and challenges.  In 2014 IEEE World Forum on Internet of Things (WF-IoT), pages 375–376, March 2014.
  * [4] F. Zhao.  Sensors meet the cloud: Planetary-scale distributed sensing and decision making.  In 9th IEEE International Conference on Cognitive Informatics (ICCI’10), pages 998–998, July 2010.
  * [5] S. Alam, M. M. R. Chowdhury, and J. Noll.  Senaas: An event-driven sensor virtualization approach for internet of things cloud.  In 2010 IEEE International Conference on Networked Embedded Systems for Enterprise Applications, pages 1–6, Nov 2010.
  * [6] N. Nikolov and O. Nakov.  Research of secure communication of esp32 iot embedded system to.net core cloud structure using mqtts ssl/tls.  In 2019 IEEE XXVIII International Scientific Conference Electronics (ET), pages 1–4, 2019.
  * [7] M. Singh, M. A. Rajan, V. L. Shivraj, and P. Balamuralidhar.  Secure mqtt for internet of things (iot).  In 2015 Fifth International Conference on Communication Systems and Network Technologies, pages 746–751, 2015.
  * [8] X. Wang, J. Zhang, E. M. Schooler, and M. Ion.  Performance evaluation of attribute-based encryption: Toward data privacy in the iot.  In 2014 IEEE International Conference on Communications (ICC), pages 725–730, 2014.
  * [9] O. H. Alhazmi and K. S. Aloufi.  Fog-based internet of things: A security scheme.  In 2019 2nd International Conference on Computer Applications Information Security (ICCAIS), pages 1–6, May 2019.
  * [10] H. Dai, Z. Zheng, and Y. Zhang.  Blockchain for internet of things: A survey.  IEEE Internet of Things Journal, 6(5):8076–8094, 2019.
  * [11] A. Niruntasukrat, C. Issariyapat, P. Pongpaibool, K. Meesublak, P. Aiumsupucgul, and A. Panya.  Authorization mechanism for mqtt-based internet of things.  In 2016 IEEE International Conference on Communications Workshops (ICC), pages 290–295, 2016.
  * [12] R. Ullah, S. H. Ahmed, and B. Kim.  Information-centric networking with edge computing for iot: Research challenges and future directions.  IEEE Access, 6:73465–73488, 2018.
  * [13] C. Perera, A. Zaslavsky, P. Christen, and D. Georgakopoulos.  Context aware computing for the internet of things: A survey.  IEEE Communications Surveys Tutorials, 16(1):414–454, First 2014\.
  * [14] K. S. Aloufi and O. H. Alhazmi.  Secure iot resources with access control over restful web services.  Jordanian Journal of Electrical Engineering, 6(1):63–77, 01 2020\.
  * [15] L. Cruz-Piris, D. Rivera, I. Mersa-Maestre, E. De la Hoz, and J. R Velasco.  Access control mechanism for iot environments based on modelling communication procedures as resources.  Sensors, 18(3):917, 2018.
  * [16] Khalid Aloufi.  6lowpan stack model configuration for iot streaming data transmission over coap.  International Journal of Communication Networks and Information Security, 11:304–3012, 08 2019.
  * [17] T. Yokotani and Y. Sasaki.  Transfer protocols of tiny data blocks in iot and their performance evaluation.  In 2016 IEEE 3rd World Forum on Internet of Things (WF-IoT), pages 54–57, 2016.
  * [18] T. Yokotani and Y. Sasaki.  Comparison with http and mqtt on required network resources for iot.  In 2016 International Conference on Control, Electronics, Renewable Energy and Communications (ICCEREC), pages 1–6, 2016.
  * [19] Thomas Hardjono, Eve Maler, Maciej Machulak, and Domenico Catalano.  User-Managed Access (UMA) Profile of OAuth 2.0.  Internet-Draft draft-hardjono-oauth-umacore-13, Internet Engineering Task Force, 2013.  Work in Progress.
  * [20] Michael Jones and Dick Hardt.  The OAuth 2.0 Authorization Framework: Bearer Token Usage.  RFC 6750, October 2012.
  * [21] Prabath Siriwardena.  Advanced API Security: Securing APIs with OAuth 2.0, OpenID Connect, JWS, and JWE.  Apress, Pittsburg, 2014.
  * [22] Eve Maler, Maciej Machulak, Justin Richer, and Thomas Hardjono.  User-Managed Access (UMA) 2.0 Grant for OAuth 2.0 Authorization.  Internet-Draft draft-maler-oauth-umagrant-00, Internet Engineering Task Force, February 2019.  Work in Progress.
  * [23] Mohammed Al-khafajiy, Thar Baker, Atif Waraich, Dhiya Al-Jumeily, and Abir Hussain.  Iot-fog optimal workload via fog offloading.  pages 359–364, 12 2018.
  * [24] S. Jaloudi.  Mqtt for iot-based applications in smart cities.  Palestinian Journal of Technology and Applied Sciences (PJTAS), 2:1–13, 03 2019.
  * [25] Maxim Osipov.  Home automation with zigbee.  In Sergey Balandin, Dmitri Moltchanov, and Yevgeni Koucheryavy, editors, Next Generation Teletraffic and Wired/Wireless Advanced Networking, pages 263–270, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.


# A Highly-Efficient Memory-Compression Scheme for GPU-Accelerated Intrusion
Detection Systems

Xavier J. A. Bellekens

Christos Tachtatzis

Robert C. Atkinson

Department of Electronic and Electrical Engineering  University of Strathclyde
Glasgow, G1 1XW, UK
<EMAIL_ADDRESS>Department of Electronic and Electrical
Engineering  University of Strathclyde  Glasgow, G1 1XW, UK
<EMAIL_ADDRESS>Department of Electronic and Electrical
Engineering  University of Strathclyde  Glasgow, G1 1XW, UK
<EMAIL_ADDRESS>Craig Renfrew

Tony Kirkham

Keysight Technologies UK  5 Lochside Avenue  Edinburgh, EH12 9DJ, GB
<EMAIL_ADDRESS>Keysight Technologies UK  5 Lochside Avenue
Edinburgh, EH12 9DJ, GB
<EMAIL_ADDRESS>
###### Abstract

Pattern Matching is a computationally intensive task used in many research
fields and real world applications. Due to the ever-growing volume of data to
be processed, and increasing link speeds, the number of patterns to be matched
has risen significantly. In this paper we explore the parallel capabilities of
modern General Purpose Graphics Processing Units (GPGPU) applications for high
speed pattern matching. A highly compressed failure-less Aho-Corasick
algorithm is presented for Intrusion Detection Systems on off-the-shelf
hardware. This approach maximises the bandwidth for data transfers between the
host and the Graphics Processing Unit (GPU). Experiments are performed on
multiple alphabet sizes, demonstrating the capabilities of the library to be
used in different research fields, while sustaining an adequate throughput for
intrusion detection systems or DNA sequencing. The work also explores the
performance impact of adequate prefix matching for alphabet sizes and varying
pattern numbers achieving speeds up to 8Gbps and low memory consumption for
intrusion detection systems.

###### category:

D.4.6 Security and protection [

###### category:

K.6.5 Management of Computing and Information Systems Security and Protection

###### keywords:

Security, GPU, CUDA, Pattern Matching, Intrusion Detection Systems

Information flow controls]

##  1 Introduction

With the exponential growth of networks, data storage, and network intrusions,
the requirement for pattern matching, virus detection, and data categorisation
poses a colossal challenge for internet service providers (ISP), and
information technology (IT) administrators. Network Intrusion Detection
Systems (NIDS) are one of the central pillars of an effective network defence
system. As such, Intrusion Detection Systems (IDS) perform intensive pattern
matching at strategic network points, or act as Host Intrusion Detection
Systems (HIDS), scanning the incoming traffic for a particular host such as
servers or end-host clients. The ever increasing prevalence of malware poses a
significant threat to privacy and security, and the constant expansion of the
link speed requires gigabit network scanning devices.

In essence, the challenge of an intrusion detection system, or a malware
scanner, is similar to the problem of efficient pattern matching. Pattern
matching is the most common task that requires most of time of the IDS, and
therefore requires an efficient algorithm both in throughput and memory
requirements [12] [11].

Typically, an IDS compare a large set of known-malicious signatures against
the potentially malicious data. Different approaches are used to cope with the
large data sets, such as the one based on specialised hardware, like field-
programmable gate arrays (FPGA) and application-specific integrated circuits
(ASIC) [2] [14]. These hardware solutions achieve good performance,
however,they are complex to customise, and are usually tied to a definitive
application, making it difficult to update the design.
On the other hand, commodity GPUs have shown their effectiveness at
accelerating pattern matching operations for virus detection systems[16] [4],
and network intrusion detection system [3] [8], while using off-the-shelf
hardware and being easily customisable to the tasks required[6][15]. Pushed
forward by the video game industry, modern GPUs are constantly maturing,
allowing flexible hardware capabilities, and powerful computational
capabilities required by intrusion detection systems. The massive number of
threads offered by the parallel capabilities of GPUs, allows them to overcome
the problems induced by their CPU counterparts and simultaneously demonstrate
better performance.

This paper addresses the problems of dealing with large signature data sets by
proposing a highly-efficient memory compression scheme, applied to a highly
parallelised multi-pattern matching algorithm, minimising the storage memory
requirements and maximising the data transfers between the host and the GPU.

The contributions of this work are fourth fold:

  * •

An efficient multi-pattern matching algorithm library is implemented and
evaluated on GPUs. The algorithm can be transposed on any other multi-threaded
system.

  * •

A highly efficient memory-compression scheme is presented, by using bitmapping
and a reduction algorithm on the trie.

  * •

An Experimentation and analysis of the algorithm over multiple alphabets is
realised, allowing the library to be used in different research fields.

  * •

An implementation and thorough analysis of prefix pattern matching over
different alphabet sizes is realised demonstrating significant speed increase
in pattern matching.

The remainder of this paper is organised as follows Section 2 presents the
background on general purpose GPU programming, and introduces multi-pattern
matching, while in Section 3 the storage model, the trie compression and the
prefix matching are presented as well as the general approach and
implementation. Furthermore Section 4 shows the experimental results obtained
with different scenarios, alphabet sizes, and prefix matching, and a
comparison of the CPU and GPU throughput is realised. The paper ends with the
conclusions and future work in Section 5.

##  2 Background

In this section basic concepts of GPUs, multi-pattern matching and related
works are reviewed.

###  2.1 GPU Programming Model

In this work the Nvidia Tesla K20m graphic card was selected, offering a rich
Software Development Kit (SDK) also known as Computer Unified Device
Architecture (CUDA) [10]. The CUDA programming model allows researchers to
harvest the massively parallel capabilities of generic consumer hardware using
a flexible abstraction model through the Nvidia SDK. To communicate with the
GPU, the C programming language has been extended with new libraries and
directives, exposing the hardware features to the researchers. The major
difference between CPUs and GPUs is based on the hardware layout. CPUs uses a
single thread based on cache hierarchy focusing on reducing the latency for
serial tasks, whereas GPUs focuses on increasing the raw processing power by
dedicating the majority of its die surface to arrays of Arithmetic Logic Units
(ALUs). The GPU is composed of several Streaming Multiprocessors (SM)
operating in a Single Instruction Multiple Thread (SIMT) fashion and are
composed of multiple Streaming Processors (SP) or CUDA cores. The number of SM
and CUDA cores are architecture dependent.

The code issued by the CPU to run on the GPU is called a kernel, and is
executed in five steps: (I) The host allocates space on the GPU to transfer
the data; (II) The data is transferred from the host memory to the GPU memory
via the DMA controller; (III) The host executes the kernel, instructing the
GPU to execute the GPU code; (IV) The GPU executes the code in a massively
parallel fashion; (V) The results are transferred back from the GPU memory to
the CPU memory via the DMA controller. Kernels are executed in parallel with a
finite number of threads. Threads are organised in thread blocks and each
streaming multiprocessor executes one or more thread blocks. Within a block,
threads are organised in warps. Warps are a group of 32 threads, and are
executed in a round robin fashion. A thread scheduler regularly switches from
one warp to another, allowing the multiprocessor to maximise the resources of
the GPU [13].

Each SP within an SM shares an instruction unit, dedicated to the management
of the instruction flow of the threads. When threads follow a different
execution path, the overall throughput of the the SM is reduced, due to the
serialisation of the instruction path. The divergent threads will be executed
first until a common instruction is found, and the remaining threads will then
converge to the same execution path [7].

Streaming multiprocessors share an off-chip L2 cache and possess their own set
of registers. Each thread in a block can also share information via the shared
memory, while all threads launched can access data using the off-chip DRAM
also called global memory. Global memory requires numerous clock cycles to be
accessed and is therefore expensive to use. Texture memory is a part of global
memory, but is read only during the execution of the kernel and only allows
defined types to be stored, however, the memory is accessed via a specific
hardware, and data pulled are cached, allowing important speed-up when data
requires numerous accesses [5].

The Tesla K20m used in this work consists of 192 CUDA cores distributed over
19 multiprocessors, in addition to each SM the L1 cache 16-48KB of memory, and
a shared memory of 16 to 48KB, both the L1 cache and shared memory must add up
to 68KB in total as they are physically the same on-chip memory. The card is
also composed of 5GB DRAM memory and consists of a single Printed Circuit
Board (PCB).

###  2.2 Multi-Pattern Matching

Pattern matching consists of searching for one or more fixed patterns $P$ in a
body of text $T$. Multi-string matching is widely used in intrusion detection
systems, and virus detection engines.
The Aho-Corasick (AC) Deterministic Finite state Automaton (DFA) is the most
popular multi-pattern matching algorithm [1]. The concept of the AC algorithm
is to maintain failure pointers that are invoked in the event of a mismatch at
the current state. Failure pointers at the first level of the trie are always
pointing back to the root node, however for the next levels the failure nodes
are computed based on the longest prefix of the pattern currently matched. If
no such prefix exists, the failure pointers point back to the root node. Each
success pointer is associated with a label, corresponding to a character of
the string and each states contains a boolean indicator expressing the status
of the previous matched node.
The matching process starts at the root node and follows the transition states
$Q$, as long as the pattern searched for is present in the text $T$. When no
corresponding valid transition state is found the pointer invokes a failure
transition, allowing to match every single pattern of the trie present in the
text $T$ in only one pass.

In a multi-threaded environment the Aho-Corasick algorithm requires the text
$T$ to be split across multiple chunks, requiring each thread to analyse
multiple chunks. This method has significant drawbacks, as a pattern may be
span two chunks of data and the algorithm would not be able to match the
pattern. Therefore overlapping is required, where each thread must scan the
entire chunk of data and overlap the next chunk by the length of the longest
pattern minus 1 [8][3]. This method also reduces the number of threads
allowed, as the number of threads launched is bound to the length of the input
text and the maximum length of the pattern. This might create bottlenecks
considering the massive number of threads able to be launched on a GPU.
Another drawback of the AC algorithm in a multi-threaded environment, is the
divergence created by the failure links, occurring when threads of the same
warps execute different portions of the code, forcing the GPU to run several
portions of the code in a serial fashion, and therefore reducing the overall
throughput of the application [8].

###  2.3 Parallel Failure-less Trie

A substitute method to parallelise the Aho-Corasick algorithm has been
designed and described by Lin et al.[8]. The Parallel Failureless Aho-Corasick
(PFAC) overcomes the problem of split patterns over two chunks of data, and
reduces the divergence by removing the failure transitions pointers from the
state machine and assigning each thread to a specific character of the text
$T$.

The parallel failure-less method harvests the full potential of the GPU by
maximising the number of threads assigned to the text $T$, and allows the
first memory transfer of the text string to happen in a coalesced manner.
Afterwards the threads will transition to separate execution paths leading to
un-coalesced memory accesses and thread divergence, however, most of them will
terminate at an early stage, as the assigned letter do not match the
signatures.
However, as the threads progresses deeper in the trie, more threads will be
discarded due to mismatches. The remaining threads matching the patterns,
leaving only a minority of threads matching, and therefore avoiding more
thread divergence.

###  2.4 Prefix Matching

To reduce the thread divergence occurring after the first level of the trie,
and speed up the matching process, the trie can be truncated to a depth of 5
for alphabets over 52 characters. This approach is known as prefix matching
and assumes that a secondary process fully matches the patterns after the
first matching stage [17].

This approach is effective due to the length of the malicious pattern and
therefore has a low probability of being a false positive. Vasiliadis et al.
[16] demonstrated that a prefix of length 8 is sufficient to produce a false
positive rate below 0.0001%.

Reducing the length of the pattern also reduces the thread divergence
occurring at deeper levels of the trie, and reduces the memory footprint due
to the number of states truncated.

Figure 1: Breadth-first constructed trie, and the bitmap corresponding to the
first node of the trie.

##  3 Design and Implementation

The library presented in this paper significantly reduces the memory footprint
of the trie, while achieving high performances throughput. To accomplish this
performance a failure-less Aho-Corasick algorithm has been implemented, along
with a reduced data structure, a highly-efficient storage model, a trie
compression algorithm and a prefix matching algorithm.

###  3.1 Storage Model

The construction of the trie is stack based, and relies on an array of
structures, allowing the trie to be stored in a continuous memory block. The
construction of the trie occurs in a breadth-first (BF) fashion, and each
pattern is added to the trie after being sorted alphabetically. The final
structure of the array has been stripped of unnecessary data and is composed
of an offset pointing to first child of the current node, or to 0 if final.
The children of each node are represented in a 256 bitmap, each bit
corresponding to one letter of the ASCII alphabet. A population count on the
bitmap is made to obtain the position of the child required.

Figure 1 shows how the nodes are organised in contiguous memory. The bitmap of
the node at cell 1 represents an array of 8 cells of 32 bits, representing the
256 ASCII alphabet. The first node ‘A’ has two children ‘B’ and ‘D’ (based on
the two first patterns). The offset of node[1] only points to its first child
(node[3]) corresponding to the letter ‘B’, however, to access the second node
‘D’ at position node[4], a population count is required. The population count,
sums the number of bits set to 1 in the bitmap, before the ASCII value of the
letter required. E.g. The letter ‘B’ corresponds to the ASCII value 66, and
letter ‘D’ corresponds to 68, meaning that the bits at position 66 and 68 are
set to 1. When an access to the node corresponding to the letter ‘D’ is
required, a population count, look up the number of bits set to one before the
corresponding ASCII value of the letter ‘D’ (68) . In this case only one bit
is set, corresponding to the letter ‘B’ at position 66. The transition is then
calculated as follows : let $i$ be the value of the population count, and
offset be the value of the first child.

$curNode=curNode\rightarrow offset+i$ (1)

As $i$ is equal to 1 and the offset of the first node ‘A’ corresponds to 3,
the second child can be found at position 3+1 =4, corresponding in Figure 1 to
node node[4].

This approach, shows that the trie only requires $4+32=36$ bytes per nodes, as
the structure only needs 32 bytes for the bitmap and 4 bytes for the offset.

The bitmap can be adapted to the size of the alphabet and occupy $|\Sigma|$
bits. Given an alphabet of $\Sigma=32$, and a corresponding bitmap size, it is
possible to compare these results against PFAC, their structure requires 15
bytes per node for a total of 24.18 MB over 1,703,023 nodes in total. The
approach described by Pungila et al. [11] using Aho-Corasick and the Commentz-
Walter (AC-CW) algorithm requires 10 bytes per node for a total of 15.02 MB,
while our approach only requires 32 bits of bitmap, and 32 bits of offset only
allowing the trie to be stored in 12.9 MB requiring 1.16 times less memory
than the AC-CW trie, and 1.87 times less memory than PFAC to store the
complete trie in memory. Comparing our method to GrAVity [16] with an alphabet
$\Sigma=256$ and a bitmap of 256 bits our storage model for a total of 352,921
nodes only requires 12.1MB while GrAVity requires 345MB, which is 28.5 times
more memory than our storage model.

Figure 2: Trie node compression.

###  3.2 Trie Compression

To further minimise the size of the trie, a compression algorithm has been
designed, allowing similar pattern suffixes to be merged, and improving the
algorithm flexibility. The reduction process consists of two major steps. The
first step consists of merging the last nodes of every pattern into a single
one and can be calculated as follows, let $Q$ be the number of states and $P$
the number of patterns :

$Q_{final}=Q-(\mid P\mid-1)$ (2)

Equation 2 allows the final number of nodes after the first step of the
reduction to be calculated. This reduction is possible as the final node of
every pattern does not possess any children, and therefore only one global
final node is required as shown in Figure 2.
The second step occurs on the last three levels of the trie, as these levels
show less divergence in the suffixes of the patterns. Merging the last levels,
allows the algorithm to significantly reduce the number of nodes.

Figure 2 shows how the reduction occurs, where the last three levels of each
pattern are compared against each other and merged when a match occurs.

The average reduction of the trie can also be calculated, considering that the
trie contains $n$ patterns and of alphabet $\Sigma$, and that all letters are
equiprobable and independent of each other. All the possible combination to
construct a chain of 2 characters is therefore calculated as follows :

$r=\Sigma^{2}$ (3)

The average reduction can then be calculated as follows, let $r$ be the number
of chains, $n$, the number of patterns $P$ the probability of a trie having
exactly $i$ unique suffixes, and $L$ the average trie length after reduction :

$\overline{L}=\sum\limits_{i=1}^{r}P(g=i)\cdot
2i=\sum\limits_{i=1}^{min(r,n)}\frac{\binom{r}{i}\left(\binom{n-i}{i}\right)}{\left(\binom{n}{r}\right)}\cdot
2i$ (4)

Equation 4 can be used to quantify the average reduction obtained by the
reduction algorithm and evaluate the memory requirements of the trie on the
GPU.

Figure 3: Prefix matching over different alphabets. Figure 4: Trie size over a
$\Sigma$ of 4. Figure 5: Trie size over a $\Sigma$ of 52.

##  4 Performance Evaluation

The series of tests conducted to evaluate the performances of this approach
have been realised using synthetic data sets randomly generated using Python
and the Mersenne Twister (MT) uniform pseudo-random numbers generator [9].

The evaluation of the algorithms is performed against 5 different data sets of
exactly 100 MB each. The uniqueness of each file is ensured by computing the
SHA256 hash of the files. Each algorithm is then run 100 times against each
data set and the results presented are the average of the total run time. This
technique permits to mitigate the sources of error, such as background
processes requesting resources.

###  4.1 Memory Hierarchies

The trie and reduction algorithms are evaluated against different numbers of
patterns and alphabet sizes. Figure 4 demonstrates the performance
improvements of the bitmapped reduced trie over the size of a simple bitmapped
trie, a binary trie and an array trie with an alphabet $\Sigma=4$ and patterns
of 20 characters. The reduction achieved by the bitmapped reduced trie
demonstrates an impressive average size reduction improvement of 38% compared
to the bitmapped trie.

Figure 5 depicts the performance of the different types of trie against an
alphabet $\Sigma=52$ and patterns of 20 chars. The increase of the alphabets
size shows that the reduction algorithm is more effective when using smaller
alphabets with synthetic files. This phenomenon is due to the lack of similar
suffixes in the randomly generated patterns over larger alphabets.

Figure 6: Prefix trie size comparison.

###  4.2 Prefix Marching Evaluation

The technique of prefix matching is alphabet dependent as the probability of a
prefix being unique is smaller when smaller alphabets are used. Figure 3
demonstrates this statement. In this evaluation 10,000 threads are launched
and the data set contains 100 patterns to be found. The patterns and the
alphabets are composed of different alphabet sizes from $\Sigma=4$ to
$\Sigma=52$.

Figure 3 shows that an alphabets of size $\Sigma=4$ will require an average
prefix of over 12 characters, before being able to match the 100 patterns
successfully. However, as the alphabet sizes rises up to $\Sigma=52$, the
prefix length dramatically decreases. The prefix matching stabilises from
$\Sigma=44$ up to larger alphabets and requires an average of 5 characters to
be matched before the validation of the prefix matching can occur. These
results verify the results of Vasiliadis et al. [16] which required prefixes
of 8 characters to successfully match the set of signature used in their
study.

Figure 6 shows the gain obtained by using a bitmapped reduced trie with prefix
matching over an alphabet of $\Sigma=52$, for 10 and 100 patterns.

###  4.3 Throughput Scaling Evaluation

In the next experiment the throughput of the algorithm is evaluated against
different alphabet sizes, and number of patterns matched. Figure 7 shows the
performance achieved by the algorithm against smaller alphabets, with a prefix
matching according to the size of the alphabet $\Sigma$. As the alphabet size
rises the throughput sustained by the matching process rises. This is due to
the number of threads being cancelled at the first matched letter. Larger
alphabets increases the number of cancelled threads, and reduce the divergence
occurring during the matching process. When matching a thousand patterns, the
throughput rises to 1 Gbps over an alphabet of 52, and when matching only one
pattern, the throughput rises to 4.6 Gbps, demonstrating an impressive
throughput for small alphabet sizes.

Figure 7: Throughput sustained for small alphabets. Figure 8: Throughput
sustained for large alphabets.

Figure 8 demonstrates the behaviour of the algorithm over larger alphabet
sizes over synthetic files. For one pattern matched the algorithm nearly
reaches 8 Gbps and for a thousand patterns, the speeds stabilises after
reaching an alphabet of $\Sigma=52$ to 1 Gbps. The number of patterns matched
are influencing the throughput of the algorithm, as the divergence created by
the higher number of patterns slows down the matching process, requiring the
GPU to perform more sequential operations.

Figure 9 shows a comparison of the throughput of CPUs and GPUs searching for
100 patterns, over an alphabet $\Sigma=52$ and files of 100 MB and 200 MB. The
size of the file do not affect the overall throughput of the algorithm, and
demonstrates a throughput of 1.3 Gbps for the GPU implementation of the
bitmapped reduced failure less trie.

Figure 9: Comparison between the throughput of the CPU and the GPU.

##  5 Conclusion

In this work we have presented an efficient bitmapped reduced failure-less
trie library for intrusion detection systems on GPUs and for applications
requiring the use of smaller alphabets such as DNA sequencing.

The experimental results presented have shown that the memory-compression
scheme in this work is ideal for GPU intrusion detection systems, using 1.87
times less memory than PFAC, over 1.16 times less memory than the AC-CW
approach, and over 28.5 times less memory than what is required in the
implementation of GrAVity. Our approach also achieved up to 8 Gbps and
demonstrated a thorough analysis of prefix matching applied to off-the-shelf
technology for varying alphabets.

Future work include real time network packet scanner on off-the-shelf
technology such as SNORT, taking advantage of multi-GPU hardware, and
improvements to the library.

## Acknowledgment

The authors would like to thank Keysight Technologies UK Ltd for their
insightful comments and feedback as well as their support.

## References

  * [1] A. V. Aho and M. J. Corasick.  Efficient string matching: An aid to bibliographic search.  Commun. ACM, 18(6):333–340, June 1975.
  * [2] M. Attig, S. Dharmapurikar, and J. Lockwood.  Implementation results of bloom filters for string matching.  In Field-Programmable Custom Computing Machines, 2004. FCCM 2004\. 12th Annual IEEE Symposium on, pages 322–323, April 2004.
  * [3] X. Bellekens, I. Andonovic, R. Atkinson, C. Renfrew, and T. Kirkham.  Investigation of GPU-based pattern matching.  In The 14th Annual Post Graduate Symposium on the Convergence of Telecommunications, Networking and Broadcasting (PGNet2013), 2013.
  * [4] Y. W. Cheng.  Fast virus signature matching based on the high performance computing of GPU.  In Communication Software and Networks, 2010. ICCSN ’10. Second International Conference on, pages 513–515, Feb 2010.
  * [5] S. Cook.  CUDA Programming: A Developer’s Guide to Parallel Computing with GPUs.  Applications of GPU Computing Series. Elsevier Science, 2012.
  * [6] N. Jacob and C. Brodley.  Offloading ids computation to the GPU.  In Computer Security Applications Conference, 2006. ACSAC ’06. 22nd Annual, pages 371–380, Dec 2006.
  * [7] D. Kirk and W. Hwu.  Programming Massively Parallel Processors: A Hands-on Approach.  Elsevier Science, 2012.
  * [8] C.-H. Lin, S.-Y. Tsai, C.-H. Liu, S.-C. Chang, and J.-M. Shyu.  Accelerating string matching using multi-threaded algorithm on GPU.  In Global Telecommunications Conference (GLOBECOM 2010), 2010 IEEE, pages 1–5, Dec 2010.
  * [9] M. Matsumoto and T. Nishimura.  Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator.  ACM Trans. Model. Comput. Simul., 8(1):3–30, Jan. 1998.
  * [10] Nvidia.  Cuda C programming guide, 2013.  http://docs.nvidia.com/cuda/.
  * [11] C. Pungila and V. Negru.  A highly-efficient memory-compression approach for GPU-accelerated virus signature matching.  In Proceedings of the 15th International Conference on Information Security, ISC’12, pages 354–369, Berlin, Heidelberg, 2012. Springer-Verlag.
  * [12] C. P. Pungila.  heterogeneous pattern matching for intrusion detection systems and digital forensics.  PhD thesis, West University of Timisoara, 2012.
  * [13] J. Sanders and E. Kandrot.  CUDA by Example: An Introduction to General-Purpose GPU Programming.  Addison-Wesley Professional, 1st edition, 2010.
  * [14] I. Sourdis and D. Pnevmatikatos.  Fast, large-scale string match for a 10gbps fpga-based network intrusion detection system.  In P. Cheung and G. Constantinides, editors, Field Programmable Logic and Application, volume 2778 of Lecture Notes in Computer Science, pages 880–889. Springer Berlin Heidelberg, 2003.
  * [15] R. Takahashi and U. Inoue.  Parallel text matching using GPGPU.  In Software Engineering, Artificial Intelligence, Networking and Parallel Distributed Computing (SNPD), 2012 13th ACIS International Conference on, pages 242–246, Aug 2012.
  * [16] G. Vasiliadis and S. Ioannidis.  Gravity: A massively parallel antivirus engine.  In S. Jha, R. Sommer, and C. Kreibich, editors, Recent Advances in Intrusion Detection, volume 6307 of Lecture Notes in Computer Science, pages 79–96. Springer Berlin Heidelberg, 2010.
  * [17] N. Yazdani and P. Min.  Prefix trees: new efficient data structures for matching strings of different lengths.  In Database Engineering and Applications, 2001 International Symposium on., pages 76–85, 2001.


#  imitation: Clean Imitation Learning Implementations

Adam Gleave1,2<EMAIL_ADDRESS>
Mohammad Taufeeque211footnotemark: 1<EMAIL_ADDRESS>
Juan Rocamonde211footnotemark: 1<EMAIL_ADDRESS>
Erik Jenner1<EMAIL_ADDRESS>
Steven H. Wang3<EMAIL_ADDRESS>
Sam Toyer1<EMAIL_ADDRESS>
Maximilian Ernestus1,2<EMAIL_ADDRESS>
Nora Belrose2<EMAIL_ADDRESS>
Scott Emmons1,2<EMAIL_ADDRESS>
Stuart Russell1<EMAIL_ADDRESS>1UC Berkeley 2FAR AI 3ETH Zurich Equal
contributionCorresponding author

###### Abstract

imitation provides open-source implementations of imitation and reward
learning algorithms in PyTorch. We include three inverse reinforcement
learning (IRL) algorithms, three imitation learning algorithms and a
preference comparison algorithm. The implementations have been benchmarked
against previous results, and automated tests cover 98% of the code. Moreover,
the algorithms are implemented in a modular fashion, making it simple to
develop novel algorithms in the framework. Our source code, including
documentation and examples, is available at
https://github.com/HumanCompatibleAI/imitation.

Keywords: Imitation Learning, Reward Learning, Software, Python, PyTorch

##  1 Introduction

Reinforcement learning (RL) has surpassed human performance in domains with
clearly-defined reward functions, such as games (Berner et al., 2019).
Unfortunately, it is difficult or impossible to procedurally specify the
reward function for many real-world tasks. We must instead _learn_ a reward
function or policy directly from user feedback. Moreover, even when we can
write down a reward function, such as if the agent wins a game, the resulting
objective might be so sparse that RL cannot efficiently solve it. State-of-
the-art results in RL therefore often use imitation learning to initialize the
policy (Vinyals et al., 2019).

We introduce imitation: a library providing high-quality, reliable and modular
implementations of seven reward and imitation learning algorithms. Crucially,
our algorithms follow a consistent interface, making it simple to train and
compare a range of algorithms. Furthermore, imitation is built using modern
backends such as PyTorch and Stable Baselines3. By contrast, prior libraries
typically support only a handful of algorithms, are no longer actively
maintained, and are built on top of deprecated frameworks.

A key use case of imitation is as an experimental _baseline_. Prior work has
shown that small implementation details in imitation learning algorithms can
have significant impacts on performance (Orsini et al., 2021). This could lead
to spurious positive results being reported if a weak experimental baseline
were used. To address this challenge, our algorithms have been carefully
benchmarked and compared to prior implementations (see Figure 1 and Table 2).
Additionally, our test suite covers 98% of our code, and we also perform
static type checking.

In addition to providing reliable baselines, imitation aims to simplify
developing novel reward and imitation learning algorithms. Our implementations
are _modular_ : users can freely change the reward or policy network
architecture, RL algorithm and optimizer without any changes to the code.
Algorithms can be extended by subclassing and overriding the relevant methods.
Moreover, to support the development of entirely novel algorithms, imitation
provides utility methods to handle common tasks such as collecting rollouts.

##  2 Features

### Comprehensive

imitation implements seven algorithms spanning a range of reward and imitation
learning styles. Our IRL algorithms consist of 1) the seminal tabular method
Maximum Causal Entropy IRL (MCE IRL; Ziebart et al., 2010), 2) a baseline
based on density estimation, and 3) the state-of-the-art approach Adversarial
IRL (AIRL; Fu et al., 2018). For imitation learning, we include 1) the simple
Behavioral Cloning (BC) algorithm, 2) a variant DAgger (Ross et al., 2011)
that learns from interactive demonstrations, and 3) the state-of-the-art
Generative Advesarial Imitation Learning (Ho and Ermon, 2016) algorithm.
Finally, we also include Deep RL from Human Preferences (DRLHP; Christiano et
al., 2017) that infers a reward function from comparisons between trajectory
fragments.

### Consistent Interface

We provide a unified API for all algorithms, inheriting from a common base
class BaseImitationAlgorithm. Algorithms diverge only where strictly necessary
(e.g. a different feedback modality). This makes it simple to automatically
test a wide range of algorithms against a benchmark suite.

### Experimental Framework

We provide scripts to train and evaluate the algorithms, making it easy to use
the library without writing a single line of code. The scripts follow a
consistent interface, and we include examples to run all algorithms on a suite
of commonly used environments. To ensure replicable experiments we use Sacred
(Greff et al., 2017) for configuration and logging.

### Modularity

To support the variety of use cases that arise in research, we have designed
our implementations to be modular and highly configurable. For example,
algorithms can be configured to use any of the seven Stable Baselines3 RL
algorithms (or a custom algorithm matching this interface). By contrast, prior
implementations often implemented imitation learning algorithms by subclassing
a specific RL algorithm, requiring substantial code modification to be ported
to new RL algorithms.

We have also designed the code to be easy to extend in order to implement
novel algorithms. Each algorithm is implemented by a class with instance
methods corresponding to each logical step of the algorithm. New algorithms
can be implemented simply by subclassing an existing algorithm and overriding
a subset of methods. This power is illustrated by our implementations of GAIL
and AIRL, which both subclass AdversarialTrainer. They differ only in the
choice of discriminator, with most training logic shared.

### Documentation

imitation comes with extensive documentation available at
https://imitation.readthedocs.io. We include installation instructions, a
quickstart guide and a contribution guide for prospective developers as well
as an API reference. We also provide tips for evaluation of imitation and
reward learning algorithms, including avoiding variable-horizon environments
which has confounded prior evaluation (Kostrikov et al., 2019).

Figure 1: Returns of our algorithms normalized so that $1$ is the returns of
an expert policy and $0$ is that of a random policy. Our algorithms reach
close to expert performance on most environments. Detailed results, including
confidence intervals, can be found in Table 2.

### High-Quality Implementations

We take great care to provide reliable implementations of algorithms. Our test
suite covers 98% of the entire codebase. Additionally, we use type annotations
throughout, and statically check our code using pytype and mypy.

While our thorough testing and code review help avoid bugs, even apparently
minor implementation details can have significant impacts on algorithm
performance (Engstrom et al., 2020). Therefore, we have also benchmarked our
algorithms on environments that have been commonly used in prior work,
including in the original papers of the algorithms.

We find in Figure 1 that our algorithms reach expert-level performance on
these environments, with the exception of AIRL in the Ant and Walker
environments, and DAgger in the Hopper environment. AIRL and DAgger were not
originally tested on the Walker and Hopper environments, respectively, so it
is possible these algorithms just do not perform well on these environments.
The AIRL paper did report positive results on an Ant environment, whereas our
implementation performs close to random. However, the AIRL paper used a custom
version of the Ant environment, whereas we use the standard Gym environment
(see Table 3 for a description of the environments used for benchmarking).

##  3 Comparison to Other Software

A key advantage of imitation is the breadth of reward and imitation learning
algorithms implemented. imitation includes a total of seven algorithms,
whereas Table 1 shows most other software packages include only one or two.
This broad coverage allows users to easily test a large number of baselines,
without needing to find and integrate multiple libraries.

Another benefit of imitation is that it is built on modern frameworks like
PyTorch and Stable Baselines3. By contrast, many extant implementations of
imitation and reward learning algorithms were released many years ago and have
not been actively maintained. This is particularly true for reference
implementations released with original papers, such as the GAIL (Ho and Hesse,
2016) and AIRL (Fu, 2018) codebases. However, even popular libraries like
Stable Baselines2 are no longer under active development111The successor to
Stable Baselines2, Stable Baselines3, has dropped support for imitation
algorithms in favour of imitation’s own implementation (Raffin et al., 2021)..

We compare alternative libraries on a variety of metrics in Table 1. Although
it is not feasible to include every implementation of imitation and reward
learning algorithms, to the best of our knowledge this table includes all
widely-used imitation learning libraries. We find that imitation equals or
surpasses alternatives in all metrics. APRel (Bıyık et al., 2021) also scores
highly but focuses on preference comparison algorithms learning from low-
dimensional features. This is complementary to imitation, which provides a
broader range of algorithms and emphasizes scalability, at the cost of greater
implementation complexity.

|  imitation |  APReL |  OpenAI Baselines |  Stable Baselines2 |  Intel COACH |  GAIL Paper |  AIRL Paper
---|---|---|---|---|---|---|---
Backend | PyTorch | NumPy | TF1 | TF1 | TF1/MxNet | Theano | TF1
# imitation algorithms | 7 | 1* | 1 | 1 | 2 | 2 | 4
Last Commit (age) | <1w | <1m | >2.5y | >3m | 1m | >4y | >4y
Approved PRs (6 months) | 103 | 0 | 0 | 1 | 7 | 0 | 0
PEP8 | ✓ | ✗ | ✓ | ✓ | ✗ | ✗ | ✗
Type Annotations | ✓ | ✓ | ✗ | ✓ | ✓ | ✗ | ✗
Type Checking | ✓ | ✗ | ✗ | ✓ | ✗ | ✗ | ✗
Test Coverage | 98% | ✗ | 49%** | 89%** | >58%** | ✗ | ✗
Documentation | ✓ | ✓ | ✗ | ✓ | ✓ | ✗ | ✗
Custom RL Agent | ✓ | N/A† | ✗§ | ✗§ | N/A† | ✗§ | ✗§
Custom Optimizer | ✓ | ✓ | ✗ | ✗ |  ¶ | ✗ | ✓
Table 1: imitation compares favourably to alternative libraries in terms of
number of imitation learning algorithms implemented, project activity,
implementation quality and flexibility. Only imitation, APReL and COACH use
modern backends.

Key: * Is a single Bayesian algorithm, but supports different feedback formats
(e.g. preference ranking and comparisons) and methods for querying feedback.
** coverage not officially reported, estimated by us from running test suite;
† does not use RL; § TRPO is the only RL algorithm supported; ¶ configurable
but limited to Adam, RMSProp and LBFGS.

Acknowledgments

Thanks to open-source contributors who have reported bugs, feature
enhancements or made code contributions. We would in particular like to thank
Yawen Duan, Lev McKinney, Nevan Wichers, Dan Pandori, Tom Tseng, Yulong Lin,
Ian Fan, Ansh Radhakrishnan and Samuel Arnesen for their code contributions.

## Author contributions

Adam Gleave managed the project, performed code reviews and made a variety of
minor code contributions. Mohammad Taufeeque benchmarked the algorithms,
improved the documentation and made other minor code contributions. Juan
Rocamonde edited the manuscript, added MyPy typing support, and made other
minor code improvements. Erik Jenner added the initial implementation of our
preference comparison algorithm. Steven H. Wang was the primary developer of
the original, TensorFlow codebase. Nora Belrose improved the documentation,
added new algorithmic features, and made minor code improvements. Sam Toyer
implemented initial versions of several algorithms and assisted with the
PyTorch port. Scott Emmons led the initial port to PyTorch and Stable
Baselines3. Stuart Russell provided research advice.

## References

  * Berner et al. (2019) Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemysław Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, Rafal Józefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique P. d. O. Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, Ilya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang.  Dota 2 with large scale deep reinforcement learning, 2019.  arXiv:1912.06680 [cs.LG].
  * Bıyık et al. (2021) Erdem Bıyık, Aditi Talati, and Dorsa Sadigh.  APReL: A library for active preference-based reward learning algorithms, 2021.
  * Christiano et al. (2017) Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei.  Deep reinforcement learning from human preferences.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , pages 4299–4307, 2017.
  * Engstrom et al. (2020) Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry.  Implementation matters in deep RL: A case study on PPO and TRPO.  In _International Conference on Learning Representations (ICLR)_ , 2020.
  * Fu (2018) Justin Fu.  Inverse RL.  https://github.com/justinjfu/inverse_rl, 2018.
  * Fu et al. (2018) Justin Fu, Katie Luo, and Sergey Levine.  Learning robust rewards with adverserial inverse reinforcement learning.  In _International Conference on Learning Representations_ , 2018.
  * Gleave et al. (2020) Adam Gleave, Pedro Freire, Steven Wang, and Sam Toyer.  seals: Suite of environments for algorithms that learn specifications.  https://github.com/HumanCompatibleAI/seals, 2020.
  * Greff et al. (2017) Klaus Greff, Aaron Klein, Martin Chovanec, Frank Hutter, and Jürgen Schmidhuber.  The Sacred infrastructure for computational research.  In _Python in Science_ , volume 28, pages 49–56, 2017.
  * Ho and Ermon (2016) Jonathan Ho and Stefano Ermon.  Generative adversarial imitation learning.  In _Advances in Neural Information Processing Systems_ , pages 4565–4573, 2016.
  * Ho and Hesse (2016) Jonathan Ho and Christopher Hesse.  Generative adversarial imitation learning.  https://github.com/openai/imitation, 2016.
  * Kostrikov et al. (2019) Ilya Kostrikov, Kumar Krishna Agrawal, Debidatta Dwibedi, Sergey Levine, and Jonathan Tompson.  Discriminator-actor-critic: Addressing sample inefficiency and reward bias in adversarial imitation learning.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Orsini et al. (2021) Manu Orsini, Anton Raichuk, Léonard Hussenot, Damien Vincent, Robert Dadashi, Sertan Girgin, Matthieu Geist, Olivier Bachem, Olivier Pietquin, and Marcin Andrychowicz.  What matters for adversarial imitation learning?, 2021.  arXiv:2106.00672 [cs.LG].
  * Raffin et al. (2021) Antonin Raffin, Ashley Hill, Maximilian Ernestus, Adam Gleave, Anssi Kanervisto, and Noah Dormann.  Imitation learning.  https://stable-baselines3.readthedocs.io/en/master/guide/imitation.html, 2021\.
  * Ross et al. (2011) Stéphane Ross, Geoffrey Gordon, and Drew Bagnell.  A reduction of imitation learning and structured prediction to no-regret online learning.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , pages 627–635, 2011.
  * Vinyals et al. (2019) Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al.  Grandmaster level in StarCraft II using multi-agent reinforcement learning.  _Nature_ , 575(7782):350–354, 2019.
  * Ziebart et al. (2010) Brian D. Ziebart, J. Andrew Bagnell, and Anind K. Dey.  Modeling interaction via the principle of maximum causal entropy.  In _International Conference on Machine Learning (ICML)_ , pages 1255–1262, 2010.

##  A Detailed benchmarking results

The table below contains a more detailed account of the results obtained
during benchmarking, including confidence intervals. The hyperparameters used
to train these algorithms can be found on the benchmarking folder of the
v0.3.2 release of imitation.

| Ant | Half Cheetah | Hopper | Swimmer | Walker
---|---|---|---|---|---
Random | $-356\pm 22$ | $-272\pm 36$ | $-60\pm 59$ | $1\pm 7$ | $-22\pm 63$
Expert | $2408\pm 110$ | $3465\pm 162$ | $2631\pm 19$ | $298\pm 1$ | $2673\pm 112$
GAIL | $2126\pm 119$ | $3010\pm 157$ | $2671\pm 27$ | $294\pm 2$ | $2643\pm 98$
AIRL | $-110\pm 37$ | $3444\pm 189$ | $2675\pm 24$ | $276\pm 6$ | $722\pm 81$
BC | $1953\pm 123$ | $3446\pm 130$ | $2243\pm 20$ | $283\pm 1$ | $2512\pm 86$
DAgger | $2321\pm 127$ | $4172\pm 104$ | $442\pm 9$ | $289\pm 2$ | $2669\pm 110$
Table 2: Benchmarking results for different algorithms and environments, in
addition to random and expert policies. Each cell contains the estimate of the
mean returns and a 95% confidence interval for a t-distribution
$t_{n-1}(\hat{\mu},\,\hat{\sigma}^{2},\,n-1)$, where $\hat{\mu}$ is the mean
returns, $\hat{\sigma}^{2}$ is an estimate of the variance of $\hat{\mu}$, and
$n$ is the number of experiments that were run, each with different seeds. In
our benchmarks, $n=5$, and for each experiment, $\approx 50$ trajectories were
collected.

##  B Environments used for benchmarking

All the environments used for benchmarking are standard Gym environments with
some modifications to the default configuration. These ship within the Seals
package (Gleave et al., 2020). MuJoCo environments from Seals are configured
to always include position in the observation and prevent early termination
when environments are unhealthy. The Half Cheetah and Swimmer environments
naturally do not terminate early, whereas the Hopper, Ant, and Walker
environments are explicitly configured to behave in this way.

The table below lists the Gym IDs of the environments, and can be loaded by
first installing Seals from PyPI.

Name | ID | Base
---|---|---
Ant | seals/Ant-v0 | Ant-v3
Half Cheetah | seals/HalfCheetah-v0 | HalfCheetah-v3
Hopper | seals/Hopper-v0 | Hopper-v3
Swimmer | seals/Swimmer-v0 | Swimmer-v3
Walker | seals/Walker2d-v0 | Walker2d-v3
Table 3: Environments used for benchmarking, including the Gym ID, and the Gym
ID of the base environment (from gym.envs.mujoco).