# The Conversation is the Command: Interacting with Real-World Autonomous
Robot Through Natural Language

Linus Nwankwo<EMAIL_ADDRESS>0000-0002-1767-2140 Chair of
Cyber-Physical Systems, MontanuniversitätFranz Josef-Straße 18, 8700
LeobenLeobenAustria8700 and  Elmar Rueckert  Chair of Cyber-Physical Systems,
MontanuniversitätFranz Josef-Straße 18, 8700 LeobenLeobenAustria
0000-0003-1221-8253

(2024; 2024)

###### Abstract.

In recent years, autonomous agents have surged in real-world environments such
as our homes, offices, and public spaces. However, natural human-robot
interaction remains a key challenge. In this paper, we introduce an approach
that synergistically exploits the capabilities of large language models (LLMs)
and multimodal vision-language models (VLMs) to enable humans to interact
naturally with autonomous robots through conversational dialogue. We leveraged
the LLMs to decode the high-level natural language instructions from humans
and abstract them into precise robot actionable commands or queries. Further,
we utilised the VLMs to provide a visual and semantic understanding of the
robot’s task environment. Our results with $99.13\%$ command recognition
accuracy and $97.96\%$ commands execution success show that our approach can
enhance human-robot interaction in real-world applications. The video
demonstrations of this paper can be found at https://osf.io/wzyf6 and the code
is available at our repository111https://github.com/LinusNEP/TCC_IRoNL.git.

Human-robot interaction, LLMs, VLMs, ChatGPT, ROS, autonomous robots, natural
language interaction.

††copyright: acmcopyright††journalyear: 2024††doi:
https://doi.org/10.1145/3610978.3640723††journalyear: 2024††copyright:
rightsretained††conference: Companion of the 2024 ACM/IEEE International
Conference on Human-Robot Interaction; March 11–14, 2024; Boulder, CO,
USA††booktitle: Companion of the 2024 ACM/IEEE International Conference on
Human-Robot Interaction (HRI ’24 Companion), March 11–14, 2024, Boulder, CO,
USA††doi: 10.1145/3610978.3640723††isbn: 979-8-4007-0323-2/24/03††ccs: Human-
centered computing††ccs: Human-centered computing††ccs: Human-centered
computing Human computer interaction (HCI)††ccs: Human-centered computing
Interaction paradigms††ccs: Human-centered computing Natural language
interfaces

##  1\. Introduction

The exploration of human-robot interaction (HRI) (Su et al., 2023), (Winkle et
al., 2023) and its advancement into real-world applications has been a topic
of significant research over the past decades (Thomaz, 2023). Current
approaches for controlling and interacting with autonomous robots in the real
world have been dominated by complex teleoperation controllers (Lin et al.,
2023), teach pendants (Akgun et al., 2012), and rigid command protocols
(Mukherjee et al., 2022), where the robots execute predefined tasks based on
specialized programming languages. As the challenges we present to these
robots become more intricate and the environments they operate in grow more
unpredictable (Nwankwo and Rueckert, 2023), there arises an unmistakable need
for more natural and intuitive interaction mechanisms.

Prior works have seen a tilt towards techniques like reinforcement (Qureshi et
al., 2018) and imitation learning (Akgun et al., 2012). By leveraging
iterative learning and human demonstrations, these strategies have shown a
capacity for fostering nuanced robot behaviours, as demonstrated in (Singh and
Heard, 2022). However, the often computational burdens (Lynch et al., 2022),
and the high costs associated with reward specification (Rocamonde et al.,
2023), task-specific training, or fine-tuning, commonly observed in the
reinforcement and imitation learning frameworks, have limited the practical
applicability of these methods, especially for simpler robotic tasks.

Figure 1. Example demonstration of our framework. We demonstrated these
results in the real world as shown in the summary video at
https://osf.io/wzyf6. In (a), our framework decodes the high-level
instructions such as “move in a circular pattern”, “move forward, go right,
etc.” from humans, and abstracts them to the robot’s physical actions. In (b),
we leveraged our framework for the robot’s task environment understanding,
information requests, and goal navigation.

These two figures (a & b) are a simulation interface showing the interaction
between a user and the robot within a virtual environment. The figure contains
a Gazebo 3D world model of an office environment and a chat window for
interacting with the robot. The Gazebo 3D world model of the office
environment is marked with different objects such as a person, chairs, tables,
and trash bins. On the right side of the figures is a chat window titled “Chat
With Robot” where a conversation is taking place between a user and a robot.
The user gives commands and asks questions, while the robot provides updates
on its position and observations. The conversation includes coordinates,
representing the robot’s location in the environment, and descriptions of the
robot’s responses, e.g., travel distance and what it can see in the
environment. The bottom part of the first figure and the top part of the
second figure show more information about the commands and the objects the
robot has detected, including their positions.

Prompted by these challenges, we turned our focus to the recent advancement in
large language models (LLMs) (Radford et al., 2019), (Brown et al., 2020) and
multi-modal vision-language models (VLMs) (Radford et al., 2021), (Ramesh et
al., 2021) to foster an intuitive human-robot collaboration. This paper
introduces an innovative approach that exploits the inherent natural language
capabilities of pre-trained LLMs and VLMs to enable humans to interact with
autonomous robots through natural language dialogues. As demonstrated in
Figure 1, we aim to realize a new approach to human-robot interactions—one
where the conversation is the command (refer to Sections 3 & 4 for more
details).

Our contributions are therefore threefold: (a) we introduced a framework that
can leverage independent pre-trained LLMs (e.g., OpenAI GPT-2 (Radford et al.,
2019) & GPT-3 (Brown et al., 2020), Google BERT (Devlin et al., 2019), Meta AI
LLaMA (Touvron et al., 2023), etc), and VLMs (e.g., CLIP(Radford et al.,
2021)) to enable real-world autonomous robots to interact with humans or other
entities using natural language dialogues. (b) we performed real-world
experiments with our developed framework to ensure that the robot’s actions
are always aligned with the user’s instructions, thereby reducing the
likelihood of erroneous operations. (c) we have made our code and associated
resources available to the public. This allows for easy reproducibility of our
results.

##  2\. Related Work

The recent rise of natural language processing (NLP) (Xie et al., 2023),
marked by large language models (LLMs) like OpenAI GPT-3 (Brown et al., 2020),
Google BERT (Devlin et al., 2019), HuggingFace distilBERT (Sanh et al., 2020),
EleutherAI GPTNeoX (Black et al., 2022), Meta AI LLaMA (Touvron et al., 2023),
Facebook RoBERTa (Liu et al., 2019), multi-modal vision-language models (VLMs)
e.g., CLIP (Radford et al., 2021), DALL-E (Ramesh et al., 2021), and their
successors, has opened new avenues for human-robot interaction. The inherent
capacity of these models to understand and generate human-like text as well as
visual observations has led to several interesting applications (Brohan et
al., 2023a), (Brohan et al., 2023b). Recent works such as (Ahn et al., 2022),
(Brohan et al., 2023b), (Huang et al., 2022) and (Kwon et al., 2023) have
successfully incorporated LLMs and VLMs into robotic systems, allowing the
LLMs to interpret and execute complex commands. Similarly, Wangchunshu et
al.(Zhou et al., 2023a), Kaiwen Zhou et al. (Zhou et al., 2023b), and Miguel
et al. (González-Santamarta et al., 2023) in their work demonstrated how LLMs
could be used to facilitate real-time feedback, zero-shot object navigation
and cognitive learning in autonomous robots.

While these works are exceptional, they have focused solely on a step-by-step
task description (Kwon et al., 2023), and rely completely on the LLM’s ability
to plan the robot’s actions and act. In most complex real-world scenarios,
especially as LLMs can sometimes hallucinate (Chen et al., 2023) or generate
inconsistent data, their approach may introduce inconsistencies and randomness
in the robot’s actions.

On the contrary, our approach draws inspiration from the work of Yagi Xie et
al. (Xie et al., 2023). Instead of relying completely on the LLMs’ ability to
plan and execute the robot’s actions, we employ a bidirectional approach,
simply using the LLMs as a linguistic decoder (Xie et al., 2023), and a
classical robot operating system (ROS) (Quigley et al., 2009) navigation
planner to plan the robot’s actions. We provide the LLMs with a dictionary of
task descriptions and action patterns. We then use the ROS
planner222https://github.com/ros-planning/navigation to plan the actual
physical actions of the robot (e.g., path planning, localisation, obstacle
avoidance, mapping, etc.), as shown in Figure 1b.

##  3\. Methods

An overview of our framework’s architecture is shown in Figure 2. One of our
core objectives is to develop a framework that enables real-world autonomous
robots to interact with humans or other entities using natural language
dialogues.

Figure 2. Overview of our framework’s architecture. The LLMNode decodes the
natural language conversations. The CLIPNode provides a visual and semantic
understanding of the robot’s task environment. The REM node abstracts the
high-level understanding from the LLMNode to actual robot actions. The ChatGUI
serves as the user’s primary interaction point. See Subsections 3.1, 3.2, and
3.3 for more details.

This figure is a flowchart describing our method’s architecture. At the top
left, a YOLO V8 detected and segmented object as well as an RGB image used as
visual inputs is shown. This data flows into “CLIPNode”, which understands
scenes using textual descriptions such as “Tables, persons, trash bins etc.”.
Adjacent to this, on the right, there’s a chat interface “ChatGUI” where a
user inputs commands and receives robot responses. Below, in the centre, are
images labelled “TF (robot’s transformation)”, “Scan (lidar data)”, and “Depth
(depth image)” used as inputs to the navigation planner. There is also a block
labelled “Robot pose” indicating the robot’s spatial orientation and odometry
data with $x,y,z$ coordinates. In the centre is the “LLMNode” for command
interpretation. Below is the “Navigation Planner” with elements for movement
control (“MoveBase”), location estimation (“Localisation”), and route creation
(“Path Planning”). Finally, on the bottom right, is the “Action (A)” section
representing the robot’s execution mechanism (REM) in the simulated
environment layout. The entire architecture illustrates the integration of
vision, large language models, and ROS planner for robot navigation.

To achieve this objective, we decompose the task into three subtasks: (a) the
integration of LLMs and VLMs, (b) the development of the robot execution
mechanism (REM) node, and (c) the development of the chat graphical user
interface (ChatGUI). An overview is shown in Figure 2. This section provides
details of each of the above three subtasks.

###  3.1. Integration of LLMs and VLMs

To decode the natural language conversation and abstract them to the robot’s
actions, we developed a ROS node, LLMNode (light green block in Figure 2) to
establish communication between the pre-trained LLMs and the rest interfaces
within ROS ecosystem (Quigley et al., 2009). The LLMNode subscribes to topics
that provide essential data, e.g., odometry for spatial sensing and outputs
from the CLIPNode (light purple block in Figure 2) for visual observation and
object recognition. We used the LLMNode to handle incoming natural language
inputs from the ChatGUI (Subsection 3.3) by first passing them through the
pre-trained LLM (Radford et al., 2019). The output is then mapped to the
robot’s actionable commands or queries.

In the mapping process, we leverage pattern matching to align the generated
text with predefined actions or information requests. For example, navigation
commands are translated into goals for the robot to pursue within its
environment, while queries $\mathcal{Q}$ about the robot’s status or
surroundings are addressed with information derived from the robot’s sensor
data. The LLMNode also oversees the execution and feedback process. We added
this function to provide real-time feedback through the publishing of
messages, which not only inform the user but also log the interaction data for
subsequent analysis (see Subsection 4.1 for more details).

Summarily, the LLMNode function can be described as a mapping from natural
language inputs to robot actions, i.e.,
$\text{LLMNode}:\mathcal{L}\mapsto\mathcal{A}$ where $\mathcal{L}$ represents
the space of natural language inputs and $\mathcal{A}$ denotes the set of
possible robot actions. This mapping is a composition of several functions, as
depicted in Eq. 1.

(1) $\text{LLMNode}(l)=\text{REM}(\text{LM}(l),\ \text{Sen}(\text{Data})),\
l\in\mathcal{L}$

From Eq. 1, $\text{LM}(l)$ is the language model’s interpretation of the input
$l_{i}\in\mathcal{L}$ and $\text{Sen}(\text{Data})$ represents the sensor data
that informs the context of the command. The REM node (Section 3.2) then
translates this into an executable command for the robot.

Furthermore, to provide a visual and semantic understanding of the task
environment (e.g., Figure 1b), we used the OpenAI contrastive language image
pretraining (CLIP) model (Radford et al., 2021). CLIP model consists of
language and image encoders trained on a staggering 400 million image-text
pairs (Schuhmann et al., 2021). Thus, we used it to encode the stream of RGB
images from our observation source (Intel Realsense D435i) alongside the
textual descriptions of objects in the image.

Formally, given an image $\mathcal{I}_{t}$ at time $t$, we consider a set of
predefined textual descriptions $\mathcal{D}=\\{d_{1},d_{2},...,d_{n}\\}$.
Each description $d_{i}\in\mathcal{D}$ is mapped to a tokenized
representation, forming a set $\mathcal{T}=\\{t_{1},t_{2},...,t_{n}\\}$. This
set encompasses human-readable labels for common office objects such as
“table”, “chair”, “person”, and so on. Using the CLIP model (Radford et al.,
2021), we extract the feature vector of the image, i.e.,
$f_{\mathcal{I}}=\text{CLIP\\_encode\\_image}(\mathcal{I}_{t})$. For each
tokenized description $t_{i}\in\mathcal{T}$, its feature vector is obtained as
$f_{\mathcal{T}_{i}}=\text{CLIP\\_encode\\_text}(t_{i})$. Subsequently, for
the image feature and every text feature, we compute the similarity scores
using $\mathcal{S}_{i}=f_{\mathcal{I}}\cdot
f_{\mathcal{T}_{i}}^{\mathcal{T}}$. Thus, we determine the recognized object
within the image by selecting the textual description that yields the highest
similarity score, as depicted in Eq. 2.

(2) $\text{Recognized Object}=t_{k};\ k=\arg\max_{i=1}^{n}\mathcal{S}_{i}$

Additionally, our model uses the bounding boxes from YOLO V8 (Jocher et al.,
2023) to determine regions of interest (ROI) within the image. Notably, the
centres of these bounding boxes are employed as the spatial coordinates for
the recognized objects, capturing both the identity and the location of the
objects in the scene.

We embodied the entire process within a ROS node, CLIPNode (light purple block
in Figure 2). The output from Eq. 2, representing the recognized objects along
with their respective spatial coordinates, is published as a ROS (Quigley et
al., 2009) topic. These are subsequently subscribed to by the LLMNode to
handle the natural language commands, generate responses, and decide on
actions for the robot to take. For instance, based on the prompt used by the
robot’s user, it can direct the robot to navigate to a detected object or
provide information about detected objects and their positions.

###  3.2. Robot Execution Mechanism (REM)

To abstract the high-level language understanding and environment sensing from
the LLMNode to actual robot actions, we developed the robot execution
mechanism (REM) node. This node translates intents extracted from the LLMNode
into actionable tasks for physical execution by the robot. Central to the REM
node’s functionality is processing navigation goals, $\mathcal{G}_{n}$ (e.g.,
Figure 1b). When a textual description of a goal destination
$\mathcal{G}_{d}$, such as “navigate to the Secretary’s office” is provided,
the REM node translates this into precise goal coordinates
$(x_{l},y_{l},z_{l},w_{l})$ within the robot’s operational environment via a
mapping process that correlates the descriptive labels with their
corresponding spatial coordinates i.e.,
$\mathcal{G}_{d}\mapsto(x_{l},y_{l},z_{l},w_{l})$. To navigate the robot to
the goal, we used the MoveBase package of the ROS navigation planner, which
provides an action server for handling navigation goals. REM node sends the
goal to this server and monitors its progress.

Besides navigation goals, the REM node also handles custom movement commands
$\mathcal{C}$ (e.g., Figure 1a) which are not tied to specific goal locations,
but rather to particular motion patterns, such as “rotate in place”, “move
forward” etc. We encoded these patterns into the robot’s YAML configuration
files, allowing for a flexible command set $c_{i}\in\mathcal{C}$ that can be
expanded or modified as required. We use the REM node to translate the
commands into Twist messages $\mathcal{W}$ with linear $(v_{x},v_{y},v_{z})$
and angular $(\omega_{x},\omega_{y},\omega_{z})$ velocity components as
$\mathcal{W}(c)=Twist(v_{x},v_{y},v_{z},\omega_{x},\omega_{y},\omega_{z})$.

In addition to handling movement, we integrated a security measure to halt the
robot when an unrecognized command (e.g., the last command in Figure 1a) is
received, issuing zero velocities to stop all motion, ensuring safe operation.

(3) $\text{REM}_{l}=\begin{cases}\mathcal{G}_{n}(l),&\text{if
}l\in\mathcal{G}_{d}\\\ \mathcal{W}(c),&\text{if }l\in\mathcal{C}\\\
\text{Sen(Data)},&\text{if }l\in\mathcal{Q}\\\ Stop(),&\text{if
}l\in\text{stop or unknown command}\\\ \end{cases}$

Formally, as summarised in Eq. 3, the REM node abstracts the complexity of the
robot navigation and command execution, translating the high-level
instructions into physical actions.

###  3.3. Chat Interface Development

To provide an intuitive conversational platform that would facilitate natural
language interaction between the robot and its human users, we developed a
simple and user-friendly chat graphical user interface (ChatGUI) which serves
as the user’s primary interaction point with the robot through textual
communication. We designed the ChatGUI using Tkinter
libraries333https://docs.python.org/3/library/tkinter.html and integrated it
within ROS (Quigley et al., 2009) for message passing. We employed the
standard ROS publish/subscribe communication mechanisms for the ChatGUI
development, specifically, a bidirectional message exchange approach, i.e.,
$\text{ChatGUI}:\text{UserInputs}\leftrightarrow\text{LLMNodeOutputs}$. User
natural language inputs are published to the LLMNode, and the responses are
subscribed to and displayed to the user on the ChatGUI interface.

We developed the ChatGUI with event-driven architecture to ensure that user
actions, such as sending a message or issuing a command, trigger corresponding
updates in the ChatGUI or result in the publishing of commands to the LLMNode.
We encapsulated this process in a function that translates user actions into
corresponding LLMNode responses.

##  4\. Preliminary Results

We conducted real-world and simulated experiments to demonstrate the
applicability and adaptability of our framework. For simulation, we used the
Unitree Go1 Gazebo packages444https://github.com/unitreerobotics/unitree_guide
and a ROS-based open-source mobile robot adapted from (Nwankwo et al., 2023).
We ran all the simulations with a ground station PC with Nvidia Geforce RTX
3060 Ti GPU, 8GB memory running Ubuntu 20.04, ROS Noetic distribution.

In real-world experiments, we used a Lenovo ThinkBook Intel Core i7 with Intel
iRIS Graphics running Ubuntu 20.04, ROS Noetic distribution. Unitree Go1
quadruped robot was used. The robot is equipped with Intel Realsense D435i
RGB-D camera and $\text{Ouster}~{}3D$ LiDAR for both visual and spatial
observations of the task environment. All the real-world experiments were
performed in our laboratory office (11 rooms) and outside corridor
environment, measuring approximately $18\times 20\;m$ and $6\times 120\;m$
respectively.

We experimented with different pre-trained open-source LLMs like OpenAI GPT-2
(Radford et al., 2019), Google BERT (Devlin et al., 2019), HuggingFace
distilBERT (Sanh et al., 2020), EleutherAI GPTNeoX (Black et al., 2022), Meta
AI LLaMA (Touvron et al., 2023), and Facebook RoBERTa (Liu et al., 2019).
OpenAI GPT-3 (Brown et al., 2020) and GPT-4 (OpenAI, 2023) are also adaptable
to our framework. However, due to their API access limitations, we mostly
utilised the open-access and free versions of the LLMs (GPT-2 (Radford et al.,
2019) specifically) in our experiments.

###  4.1. Initial Evaluation / Participants

In our initial evaluation, we invited $21$ participants (mostly students) with
an average age of $23\ (\pm 5)$ and gender distribution, $61.9\%$ male,
$28.6\%$ female and $9.5\%$ others to assess the intuitiveness of our
framework by interacting with the robots using natural language. We instructed
the participants to command the robots to navigate to locations, identify
objects, and inquire about their status. We meticulously logged the
interaction data which includes the participant’s input text, the LLM’s
output, the true label, the LLMNode predicted label, etc. To quantitatively
evaluate the performance of our framework, we established four key metrics:

(a) Command Recognition Accuracy (CRA): With the CRA, we assess how accurately
the LLMNode interprets the natural language commands. This aids us in
pinpointing instances where the predicted label diverged from the true label,
providing insights into potential areas for improvement. (b) Object
Identification Accuracy (OIA): We employed this metric to assess the precision
of the CLIPNode in identifying and localizing objects within the robot’s task
environment. (c) Navigation Success Rate (NSR): We utilised this metric to
determine the effectiveness of the REM node in successfully navigating the
robot to the designated locations. (d) Average Response Time (ART): We logged
in ROS Unix epoch clock standard, the time a message is sent from the ChatGUI,
the time it is received by the LLMNode, and the time the robot responds. With
the ART, we compute the average duration from receiving the user’s chat
command to initiating the robot’s movement.
Figure 3 presents our preliminary statistical results obtained from the
interaction data analysis. The top row of Figure 3 shows the performance
metrics and the confusion matrix (for selected labels) of the LLMNode. The
CRA, with a prediction accuracy of $99.13\%$ (i.e., how often the “Predicted
labels” matched the “True labels”), indicates a high level of accuracy in the
command interpretation. This reflects the robustness of the LLMNode in
processing the natural language inputs. The OIA on the other hand, achieved
$55.20\%$ accuracy, indicating room for improvement in our CLIPNode
integration. Further, the NSR at $97.96\%$, indicates good performance in the
REM’s ability to abstract the high-level understanding from the LLMNode to the
actual robot’s navigation actions.

Figure 3. Performance and variability measures illustrating CRA, OIA, and NSR
(top) and the participants’ feedback (bottom) based on the logged interaction
data.

This figure shows a statistical analysis of interaction data logged from
participants’ interactions with the robot. At the top left is a bar chart with
three different metrics for accessing the performance accuracy of our
framework which includes the command recognition accuracy (CRA), object
identification accuracy (OIA), and the navigation success rate (NSR). The CRA
and NSR have very high-performance percentages, 99.13% and 97.96%
respectively, whereas OIA has a significantly lower performance at 55.20%. The
top right features a confusion matrix table used to describe how the LLMNode
predicted labels diverge from the true labels. Each cell in the matrix shows a
number, with a scale from $0.0$ to $1.0$, where $1.0$ represents a perfect
match between the predicted and the true label. The bottom row shows a stacked
bar chart displaying ratings from participants from different occupation
distributions like Engineer, Technician, Student, and others. Five aspects are
rated on a scale from $1$ to $5$, such as familiarity with technology, ease of
interacting with the robot, command understanding accuracy, intuitiveness of
the framework, and satisfaction with the robot’s response to commands.
Engineers and Technicians gave the highest ratings across all aspects, while
Students and Researchers varied, with some aspects rated as low as 3.5.
Apprentices and Logistics participants gave middle-ground ratings, no lower
than 3.5 and no higher than 4.5.

Also, the overall ART across all the selected commands (refer to the figure at
https://osf.io/ufctx) is approximately 0.45 seconds. This indicates that, on
average, the robot takes less than half a second from receiving a chat command
to initiating movement, which suggests a relatively quick response time for
our framework.

Furthermore, the bottom row of Figure 3 shows the participants’ feedback
(refer to the questionnaire at https://osf.io/dgbtr). With $4$ and $5$ ratings
as favourable benchmarks, $80.9\%$ and $76.2\%$ of the participants
respectively rated the ease of interaction and the intuitiveness of our
framework as favourable, while $85.7\%$ are satisfied with the response of the
robot to their natural language commands.

##  5\. Conclusion and Future Work

We introduced a framework that leverages the inherent capabilities of large
language models (LLMs) and multimodal vision-language models (VLMs) to enhance
human-robot interaction through natural conversation. Our evaluation from the
logged interaction data and participants’ feedback was overwhelmingly
positive. The high command recognition accuracy and effective task execution,
show that our framework can simplify human-robot interaction. Looking ahead,
we aim to refine the framework across several dimensions, not just for ROS-
based autonomous robots. The CLIPNode will be further improved for broader
object recognition, and the LLMNode will be fine-tuned with domain-specific
data for better contextual and voice understanding. User experience will be a
priority, with a focus on creating a more intuitive and adaptive chat
interface.

## References

  * (1)
  * Ahn et al. (2022) Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Daniel Ho, Jasmine Hsu, Julian Ibarz, Brian Ichter, Alex Irpan, Eric Jang, Rosario Jauregui Ruano, Kyle Jeffrey, Sally Jesmonth, Nikhil J Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang, Kuang-Huei Lee, Sergey Levine, Yao Lu, Linda Luu, Carolina Parada, Peter Pastor, Jornell Quiambao, Kanishka Rao, Jarek Rettinghouse, Diego Reyes, Pierre Sermanet, Nicolas Sievers, Clayton Tan, Alexander Toshev, Vincent Vanhoucke, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, Mengyuan Yan, and Andy Zeng. 2022.  Do As I Can, Not As I Say: Grounding Language in Robotic Affordances.  arXiv:2204.01691 [cs.RO]
  * Akgun et al. (2012) Baris Akgun, Maya Cakmak, Jae Wook Yoo, and Andrea Lockerd Thomaz. 2012.  Trajectories and Keyframes for Kinesthetic Teaching: A Human-Robot Interaction Perspective. In _Proceedings of the Seventh Annual ACM/IEEE International Conference on Human-Robot Interaction_ (Boston, Massachusetts, USA) _(HRI ’12)_. Association for Computing Machinery, New York, NY, USA, 391–398.  https://doi.org/10.1145/2157689.2157815
  * Black et al. (2022) Sid Black, Stella Biderman, Eric Hallahan, Quentin Anthony, Leo Gao, Laurence Golding, Horace He, Connor Leahy, Kyle McDonell, Jason Phang, Michael Pieler, USVSN Sai Prashanth, Shivanshu Purohit, Laria Reynolds, Jonathan Tow, Ben Wang, and Samuel Weinbach. 2022.  GPT-NeoX-20B: An Open-Source Autoregressive Language Model.  arXiv:2204.06745 [cs.CL]
  * Brohan et al. (2023a) Anthony Brohan, Noah Brown, Justice Carbajal, Yevgen Chebotar, Xi Chen, Krzysztof Choromanski, Tianli Ding, Danny Driess, Avinava Dubey, Chelsea Finn, Pete Florence, Chuyuan Fu, Montse Gonzalez Arenas, Keerthana Gopalakrishnan, Kehang Han, Karol Hausman, Alexander Herzog, Jasmine Hsu, Brian Ichter, Alex Irpan, Nikhil Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang, Isabel Leal, Lisa Lee, Tsang-Wei Edward Lee, Sergey Levine, Yao Lu, Henryk Michalewski, Igor Mordatch, Karl Pertsch, Kanishka Rao, Krista Reymann, Michael Ryoo, Grecia Salazar, Pannag Sanketi, Pierre Sermanet, Jaspiar Singh, Anikait Singh, Radu Soricut, Huong Tran, Vincent Vanhoucke, Quan Vuong, Ayzaan Wahid, Stefan Welker, Paul Wohlhart, Jialin Wu, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, Tianhe Yu, and Brianna Zitkovich. 2023a.  RT-2: Vision-Language-Action Models Transfer Web Knowledge to Robotic Control.  arXiv:2307.15818 [cs.RO]
  * Brohan et al. (2023b) Anthony Brohan, Noah Brown, Justice Carbajal, Yevgen Chebotar, Joseph Dabis, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Jasmine Hsu, Julian Ibarz, Brian Ichter, Alex Irpan, Tomas Jackson, Sally Jesmonth, Nikhil J Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang, Isabel Leal, Kuang-Huei Lee, Sergey Levine, Yao Lu, Utsav Malla, Deeksha Manjunath, Igor Mordatch, Ofir Nachum, Carolina Parada, Jodilyn Peralta, Emily Perez, Karl Pertsch, Jornell Quiambao, Kanishka Rao, Michael Ryoo, Grecia Salazar, Pannag Sanketi, Kevin Sayed, Jaspiar Singh, Sumedh Sontakke, Austin Stone, Clayton Tan, Huong Tran, Vincent Vanhoucke, Steve Vega, Quan Vuong, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, Tianhe Yu, and Brianna Zitkovich. 2023b.  RT-1: Robotics Transformer for Real-World Control at Scale.  arXiv:2212.06817 [cs.RO]
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language Models are Few-Shot Learners.  arXiv:2005.14165 [cs.CL]
  * Chen et al. (2023) Yuyan Chen, Qiang Fu, Yichen Yuan, Zhihao Wen, Ge Fan, Dayiheng Liu, Dongmei Zhang, Zhixu Li, and Yanghua Xiao. 2023.  Hallucination Detection: Robustly Discerning Reliable Answers in Large Language Models. In _Proceedings of the 32nd ACM International Conference on Information and Knowledge Management_ (Birmingham, United Kingdom) _(CIKM ’23)_. Association for Computing Machinery, New York, NY, USA, 245–255.  https://doi.org/10.1145/3583780.3614905
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  arXiv:1810.04805 [cs.CL]
  * González-Santamarta et al. (2023) Miguel Á. González-Santamarta, Francisco J. Rodríguez-Lera, Ángel Manuel Guerrero-Higueras, and Vicente Matellán-Olivera. 2023.  Integration of Large Language Models within Cognitive Architectures for Autonomous Robots.  arXiv:2309.14945 [cs.RO]
  * Huang et al. (2022) Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch. 2022.  Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents.  arXiv:2201.07207 [cs.LG]
  * Jocher et al. (2023) Glenn Jocher, Ayush Chaurasia, and Jing Qiu. 2023.  _Ultralytics YOLOv8_.  https://github.com/ultralytics/ultralytics
  * Kwon et al. (2023) Teyun Kwon, Norman Di Palo, and Edward Johns. 2023.  Language Models as Zero-Shot Trajectory Generators.  arXiv:2310.11604 [cs.RO]
  * Lin et al. (2023) Tsung-Chi Lin, Achyuthan Unni Krishnan, and Zhi Li. 2023.  Perception-Motion Coupling in Active Telepresence: Human Behavior and Teleoperation Interface Design.  _J. Hum.-Robot Interact._ 12, 3, Article 31 (mar 2023), 24 pages.  https://doi.org/10.1145/3571599
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.  arXiv:1907.11692 [cs.CL]
  * Lynch et al. (2022) Corey Lynch, Ayzaan Wahid, Jonathan Tompson, Tianli Ding, James Betker, Robert Baruch, Travis Armstrong, and Pete Florence. 2022.  Interactive Language: Talking to Robots in Real Time.  arXiv:2210.06407 [cs.RO]
  * Mukherjee et al. (2022) Debasmita Mukherjee, Kashish Gupta, and Homayoun Najjaran. 2022.  A Critical Analysis of Industrial Human-Robot Communication and Its Quest for Naturalness Through the Lens of Complexity Theory.  _Frontiers in Robotics and AI_ 9 (2022).  https://doi.org/10.3389/frobt.2022.870477
  * Nwankwo et al. (2023) Linus Nwankwo, Clemens Fritze, Konrad Bartsch, and Elmar Rueckert. 2023.  ROMR: A ROS-based open-source mobile robot.  _HardwareX_ 14 (2023), e00426.  https://doi.org/10.1016/j.ohx.2023.e00426
  * Nwankwo and Rueckert (2023) Linus Nwankwo and Elmar Rueckert. 2023.  Understanding Why SLAM Algorithms Fail in Modern Indoor Environments. In _Advances in Service and Industrial Robotics_ , Tadej Petrič, Aleš Ude, and Leon Žlajpah (Eds.). Springer Nature Switzerland, Cham, 186–194.
  * OpenAI (2023) OpenAI. 2023.  GPT-4 Technical Report.  arXiv:2303.08774 [cs.CL]
  * Quigley et al. (2009) Morgan Quigley, Ken Conley, Brian Gerkey, Josh Faust, Tully Foote, Jeremy Leibs, Rob Wheeler, and Andrew Ng. 2009.  ROS: an open-source Robot Operating System.  _ICRA Workshop on Open Source Software_ 3\.
  * Qureshi et al. (2018) Ahmed Hussain Qureshi, Yutaka Nakamura, Yuichiro Yoshikawa, and Hiroshi Ishiguro. 2018.  Intrinsically motivated reinforcement learning for human–robot interaction in the real-world.  _Neural Networks_ 107 (2018), 23–33.  https://doi.org/10.1016/j.neunet.2018.03.014 Special issue on deep reinforcement learning.
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. 2021.  Learning Transferable Visual Models From Natural Language Supervision.  arXiv:2103.00020 [cs.CV]
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language Models are Unsupervised Multitask Learners.  https://api.semanticscholar.org/CorpusID:160025533
  * Ramesh et al. (2021) Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. 2021.  Zero-Shot Text-to-Image Generation.  arXiv:2102.12092 [cs.CV]
  * Rocamonde et al. (2023) Juan Rocamonde, Victoriano Montesinos, Elvis Nava, Ethan Perez, and David Lindner. 2023.  Vision-Language Models are Zero-Shot Reward Models for Reinforcement Learning.  arXiv:2310.12921 [cs.LG]
  * Sanh et al. (2020) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2020.  DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter.  arXiv:1910.01108 [cs.CL]
  * Schuhmann et al. (2021) Christoph Schuhmann, Richard Vencu, Romain Beaumont, Robert Kaczmarczyk, Clayton Mullis, Aarush Katta, Theo Coombes, Jenia Jitsev, and Aran Komatsuzaki. 2021.  LAION-400M: Open Dataset of CLIP-Filtered 400 Million Image-Text Pairs.  arXiv:2111.02114 [cs.CV]
  * Singh and Heard (2022) Saurav Singh and Jamison Heard. 2022.  Human-Aware Reinforcement Learning for Adaptive Human Robot Teaming. In _Proceedings of the 2022 ACM/IEEE International Conference on Human-Robot Interaction_ (Sapporo, Hokkaido, Japan) _(HRI ’22)_. IEEE Press, 1049–1052.
  * Su et al. (2023) Hang Su, Wen Qi, Jiahao Chen, Chenguang Yang, Juan Sandoval, and Med Amine Laribi. 2023.  Recent advancements in multimodal human–robot interaction.  _Frontiers in Neurorobotics_ 17 (2023).  https://doi.org/10.3389/fnbot.2023.1084000
  * Thomaz (2023) Andrea Thomaz. 2023.  Robots in Real Life: Putting HRI to Work. In _Proceedings of the 2023 ACM/IEEE International Conference on Human-Robot Interaction_ (Stockholm, Sweden) _(HRI ’23)_. Association for Computing Machinery, New York, NY, USA, 3.  https://doi.org/10.1145/3568162.3578810
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023.  LLaMA: Open and Efficient Foundation Language Models.  arXiv:2302.13971 [cs.CL]
  * Winkle et al. (2023) Katie Winkle, Erik Lagerstedt, Ilaria Torre, and Anna Offenwanger. 2023.  15 Years of (Who)Man Robot Interaction: Reviewing the H in Human-Robot Interaction.  _J. Hum.-Robot Interact._ 12, 3, Article 28 (apr 2023), 28 pages.  https://doi.org/10.1145/3571718
  * Xie et al. (2023) Yaqi Xie, Chen Yu, Tongyao Zhu, Jinbin Bai, Ze Gong, and Harold Soh. 2023.  Translating Natural Language to Planning Goals with Large-Language Models.  arXiv:2302.05128 [cs.CL]
  * Zhou et al. (2023b) Kaiwen Zhou, Kaizhi Zheng, Connor Pryor, Yilin Shen, Hongxia Jin, Lise Getoor, and Xin Eric Wang. 2023b.  ESC: Exploration with Soft Commonsense Constraints for Zero-Shot Object Navigation. In _Proceedings of the 40th International Conference on Machine Learning_ (Honolulu, Hawaii, USA) _(ICML’23)_. JMLR.org, Article 1806, 14 pages.
  * Zhou et al. (2023a) Wangchunshu Zhou, Yuchen Eleanor Jiang, Long Li, Jialong Wu, Tiannan Wang, Shi Qiu, Jintian Zhang, Jing Chen, Ruipu Wu, Shuai Wang, Shiding Zhu, Jiyu Chen, Wentao Zhang, Ningyu Zhang, Huajun Chen, Peng Cui, and Mrinmaya Sachan. 2023a.  Agents: An Open-source Framework for Autonomous Language Agents.  arXiv:2309.07870 [cs.CL]


11institutetext: Piero Bonatti 22institutetext: Iliana M. Petrova
33institutetext: Luigi Sauro 44institutetext: Università di Napoli Federico
II, Naples, Italy
44email<EMAIL_ADDRESS>55institutetext: Sabrina Kirrane 66institutetext: Vienna
University of Economics and Business, Vienna, Austria
66email<EMAIL_ADDRESS>
# Machine Understandable Policies and GDPR Compliance Checking

Piero A. Bonatti  Sabrina Kirrane  Iliana M. Petrova  Luigi Sauro

(Received: 31st October 2019 / Accepted: tba)

###### Abstract

The European General Data Protection Regulation (GDPR) calls for technical and
organizational measures to support its implementation. Towards this end, the
SPECIAL H2020 project aims to provide a set of tools that can be used by data
controllers and processors to automatically check if personal data processing
and sharing complies with the obligations set forth in the GDPR. The primary
contributions of the project include: (i) a policy language that can be used
to express consent, business policies, and regulatory obligations; and (ii)
two different approaches to automated compliance checking that can be used to
demonstrate that data processing performed by data controllers / processors
complies with consent provided by data subjects, and business processes comply
with regulatory obligations set forth in the GDPR.

##  1 Introduction

The European General Data Protection Regulation (GDPR), which came into force
on the 25th of May 2018, defines legal requirements concerning the processing
and sharing of personally identifiable data. In addition, the legislation
calls for technical and organizational measures to support its implementation.

When it comes to legal informatics there is a large body of work on legal
knowledge representation and reasoning (cf., Bartolini et al. (2015); Pandit
et al. (2018); Palmirani et al. (2011); Athan et al. (2013); Governatori et
al. (2016); Lam and Hashmi (2019)), however said approaches are usually
foundational in nature and as such are not readily accessible for companies
looking for technical means to demonstrate GDPR compliance.

Recently we have seen the emergence of GDPR compliance tools (cf., Information
Commissioner’s Office UK(2017) (ICO); Microsoft Trust Center (2017); Nymity ;
Agarwal et al. (2018)) in the form of predefined questionnaires that enable
data controllers and processors to assess the compliance of services and
products that process personal data. The primary limitation of said tools is
their lack of support for automated compliance checking.

In order to fill this gap, SPECIAL builds upon a rich history of policy
language research from the Semantic Web community (cf., Woo and Lam (1993);
Jajodia et al. (2001); Uszok et al. (2003); Kagal et al. (2003); Bonatti et
al. (2010)), and shows how together machine understandable policies and
automated compliance checking can be used to demonstrate compliance with legal
requirements set forth in the GDPR.

In particular, we introduce the SPECIAL policy language and discuss how it can
be used to express consent, business policies, and regulatory obligations. In
addition, we describe two different approaches to automated compliance
checking used to demonstrate that: (i) data processing performed by data
controllers / processors complies with consent provided by data subjects; and
(ii) business processes comply with regulatory obligations set forth in the
GDPR. In addition, we provide a highlevel overview of our compliance checking
algorithm and present the results of our initial performance evaluation.

The remainder of the paper is structured as follows: _Section_ 2 describes our
analysis of the text of the GDPR. _Section_ 3 introduces the SPECIAL policy
language, which provides a machine understandable encoding of consent.
_Section_ 4 discusses how the SPECIAL policy language can be used to encode
business policies and regulatory obligations. _Section_ 5 presents our
compliance checking algorithm and the results of our initial performance
evaluation. _Section_ 6 points to related work on GDPR compliance. Finally, we
present our conclusions and interesting directions for future work in
_Section_ 7.

##  2 Requirements Analysis

One of the primary goals of SPECIAL is to automatically check if personal data
processing and sharing performed by data controllers and processors complies
with obligations set forth in the GDPR. A necessary first step is to better
understand the text of the GDPR, its interpretation by legal professionals,
and the role of machine understandable representations, and automated
compliance checking.

###  2.1 GDPR Analysis

Legal rules are composed of several constructs, prohibitions (used to describe
what is not permitted), permissions (used to describe what is permitted),
obligations (used to describe requirements that must be fulfilled), and
dispensations (used to describe exemptions), commonly referred to as deontic
concepts. In addition to these common constructs, the legal language contains
constraints (used to limit the scope of permissions, prohibitions, obligations
and dispensations), definitions (used to establish meaning), dispositions
(used to highlight best practices/ suggestions), and opening clauses (used to
indicate the need to consult National or European legislation). When it comes
to encoding legislative requirements using machine understandable
representations, such that it is possible to perform automated compliance,
major considerations include:

#### Connectedness

of the various articles, paragraphs, and points, which can either explicitly
refer to another piece of legislation (e.g., _scientific or historical
research purposes or statistical purposes in accordance with Article 89(1)_)
or implicitly to knowledge about the law (e.g., _Personal data shall be: (a)
processed lawfully, fairly and in a transparent manner in relation to the data
subject (’lawfulness, fairness and transparency’)_). In either case, from an
automated compliance checking perspective, it is clear that legal requirements
are not separate and distinct rules but rather rules need to be linked,
clustered, and/or generalized in a manner that enables the validation of a
combination rules. In SPECIAL we do not try to encode the entire GDPR, but
rather focus on encoding legislative obligations (relating to several
articles, paragraphs, and points) such that: (i) data processing performed by
data controllers / processors complies with consent provided by data subjects;
and (ii) business processes comply with regulatory obligations set forth in
the GDPR.

#### Temporal expressions

provide contextual information that is relevant for the interpretation of
actions that need to be taken. Several different types of temporal expressions
can be found in the text of the GDPR, for instance:

  * •

… _the right to withdraw his or her consent at any time_ (Article 7 paragraph
3);

  * •

… _processing based on consent before its withdrawal_ (Article 7 paragraph 3,
Article 13 paragraph 2, Article 14 paragraph 2);

  * •

… _prior to giving consent_ (Article 7 paragraph 3);

  * •

… _at the time when personal data are obtained_ (Article 13 paragraphs 1 and
2);

  * •

… _the personal data shall no longer be processed_ (Article 21 paragraph 3);

In SPECIAL we provide support for such temporal requirements by recording in a
suitable _transparency ledger_ when consent was obtained or when the data
processing/sharing happened. This information is used for both ex-ante and ex-
post compliance checking (as well as other purposes, discussed later).

###  2.2 Legal Interpretations

The GDPR defines several potential legal bases (consent, contract, legal
obligation, vital interest, public interest, exercise of official authority,
and legitimate interest) under which companies can legally process personal
data. In order to determine if personal data processing is legally valid, the
legal inquiry process usually involves gathering specific information such as:
(i) the _personal data_ collected from the data subject;  (ii) the
_processing_ that are performed on the personal data;  (iii) the _purpose_ of
such processing;  (iv) where data are _stored and for how long_ ; and  (v)
with whom data is _shared_.  The answers provided to said questions enable
legal professionals to determine which articles need to be consulted in order
both to assess the lawfulness of processing and to identify relevant legal
obligations.

Although, the open textured nature of legal texts is a highly desirable
feature, as it leaves room for interpretation on a case by case basis, such
ambiguity poses challenges for automatic compliance checking. In terms of
legal interpretations, legal professionals also need to interpret the facts of
the case with respect to relevant National or European legislation (e.g.,
opening clauses) and subjective terms (e.g., single words or parts of a
sentence that can be interpreted in various ways). Here legal knowledge graphs
could potentially play a crucial role as they allow for the modeling of both
legislation and cases in a machine readable format, based on standardization
activities such as European Law Identifier (ELI) and the European Case Law
Identifier (ECLI), which provide technical specifications for web identifiers
and vocabularies that can be used to describe metadata pertaining to legal
documents. Such a legal knowledge graph could be used not only to identify
case specific legislation, but also to uncover if there have been any prior
cases that could be used to reduce ambiguity. The SPECIAL poly language has
been developed together with legal professionals who well versed in the
interpretation of legal texts. Going forward we envisage that legal knowledge
graphs could be used to reduce subjectivity thus allowing us to perform
automated compliance checking for a broader set of legislative requirements.

###  2.3 Machine Understandable Representations

The GDPR poses at least two requirements that call for a machine-
understandable representation of data usage modalities. Article 30 states that
each controller shall maintain a record of the personal data processing
activities under its responsibility. The first paragraph specifies that such a
ledger should describe (among other information) the following aspects of
_data usage_ :

  * P1.

the _purpose_ of processing;

  * P2.

a description of the _categories of data subjects_ and of the _categories of
personal data_ ;

  * P3.

the categories of _recipients_ to whom the personal data have been or will be
disclosed;

  * P4.

_transfers_ of personal data to a third country or an international
organization (since cross-border data transfer are subject to limitations);

  * P5.

the envisaged _time limits for erasure_ of the different categories of data;

  * P6.

information about the _processing_ , such as the security measures mentioned
in Article 32.

Recital 42 stresses that, where processing is based on the data subject’s
consent, the controller should be able to demonstrate that the data subject
has given consent to the processing operation. SPECIAL addresses this issue by
recording consent in the transparency ledger (cf. Sec. 2.1). The description
of consent is similar to the description of processing activities as per
Article 30. While Article 6.1.(a) – that introduces consent as a legal basis
for personal data processing – and Recital 42 explicitly mention only the
purpose of processing, Articles 13 and 14 add the other elements P2–P6 listed
above. Concerning P6 (processing), it should be specified whether any
automated decision making is involved, including profiling.

###  2.4 Automated Compliance Checking

Once such data usage descriptions are encoded in a machine-understandable way,
several tasks, related to GDPR compliance, can be automated, including:

  * T1.

Checking whether the processing complies with several restrictions imposed by
the GDPR, such as additional requirements on the processing of sensitive data,
restrictions on cross-border transfers, and compatibility of data usage with
the chosen legal basis. This kind of validation requires a machine-
understandable formalization of the relevant parts of the GDPR.

  * T2.

Checking whether a specific operation is permitted by the available consent.

  * T3.

Running ex-post auditing on the controller’s activities. In SPECIAL this task
is supported by logging data processing events in the transparency ledger, and
comparing such events with consent.

  * T4.

Finding the consent that justifies a specific processing (for auditing or
responding to a data subject’s inquiry).

The transparency ledger is also used in SPECIAL to provide dashboards to data
subjects, that support them in monitoring the use of their data and
_explaining_ why their consent allowed specific operations. Such dashboards
can also be used as a uniform interface to let data subjects exercise their
rights (access to data, right to erasure, etc.) as specified by Articles 15–18
and 21–22.

##  3 Consent Compliance Checking

Although there are several potential legal bases that could be used to
lawfully process personal data, in SPECIAL we have a particular focus on
consent. Thus in this section we present the SPECIAL policy language and
demonstrate how it can be used to encode consent in a manner than enables
automated compliance checking.

###  3.1 Encoding Usage Descriptions and Consent

The common structure of the activity records and of the consent forms,
consisting of properties P1–P6, is called _simple (usage) policy_ in SPECIAL.
In general, both the controller’s activities and the consent of data subjects
can be described by a _set_ of simple usage policies (covering different data
categories and purposes), called _full (usage) policies_. Each simple policy
can be specified simply by attaching to each property Pi (such as purpose,
data category, recipients, etc.) a term selected from a suitable _vocabulary_
(ontology).

###### Example 1

A company – call it BeFit – sells a wearable fitness appliance and wants (i)
to process biometric data (stored in the EU) for sending health-related advice
to its customers, and (ii) share the customer’s location data with their
friends. Location data are kept for a minimum of one year but no longer than
5; biometric data are kept for an unspecified amount of time. In order to do
all this legally, BeFit needs consent from its customers. Consent can be
represented with two simple policies, specified using SPECIAL’s vocabularies:

      {
        has_purpose: FitnessRecommendation,
        has_data: BiometricData,
        has_processing: Analytics,
        has_recipient: BeFit,
        has_storage: { has_location: EU }
      }

      {
        has_purpose: SocialNetworking,
        has_data: LocationData,
        has_processing: Transfer,
        has_recipient: DataSubjFriends,
        has_storage: {
            has_location: EU,
            has_duration: [1year,5year]
            }
      }

If HeartRate is a subclass of BiometricData and ComputeAvg is a subclass of
Analytics, then the above consent allows BeFit to compute the average heart
rate of the data subject in order to send her fitness recommendations. BeFit
customers may restrict their consent, e.g. by picking a specific
recommendation modality, like “recommendation via SMS only”. Then the first
line should be replaced with something like:

      has_purpose:{
        FitnessRecommendation,
        contact: SMS}

Moreover, a customer of BeFit may consent to the first or the second argument
of the union, or both. Their consent would be encoded, respectively, with the
first simple policy, the second simple policy, or both. Similarly, each single
process in the controller’s business application may use only biometric data,
only location data, or both. Accordingly, it may be associated to the first
simple policy, the second simple policy, or both.

The temporary exemplifying policy language vocabularies reported in SPECIAL’s
deliverables have been obtained by adapting previous standardized terms
introduced by initiatives related to privacy and digital rights management,
such as P3P111http://www.w3.org/TR/P3P11 and
ODRL,222https://www.w3.org/TR/odrl/. More refined vocabularies have been
recently proposed by W3C’s _Data Privacy Vocabularies and Controls Community
Group_ , (DPVCG) Pandit et al. (2019), promoted by SPECIAL and spanning a
range of stakeholders wider than the project’s consortium. The current
vocabularies can be found on DPVCG’s website333www.w3.org/community/dpvcg/.

As shown in Example 1, usage policies can be formatted with a minor extension
of JSON (in particular, compound terms and policy sets require additional
operators), while vocabularies can be encoded in RDFS or lightweight profiles
of OWL2 such as OWL2-EL and OWL2-QL.

A grammar for SPECIAL policy expressions in Backus–Naur form (BNF) format is
presented in Figure 1. The categories DataVocabExpression,
PurposeVocabExpression, ProcessingVocabExpression, RecipientVocabExpression,
LocationVocabExpression, DurationVocabExpression are specified by DPVCG’s
vocabularies.

Figure 1: SPECIAL’s Usage Policy Language Grammar

UsagePolicy $\mathbf{\mathrel{\mathop{:}}=}$’ObjectUnionOf’ ’(’
BasicUsagePolicy
{ BasicUsagePolicy }* ’)’
$\;\mid\;$ BasicUsagePolicy
BasicUsagePolicy $\mathbf{\mathrel{\mathop{:}}=}$’ObjectIntersectionOf’ ’(’
Data Purpose Processing Recipients Storage ’)’
Data $\mathbf{\mathrel{\mathop{:}}=}$’ObjectSomeValueFrom’ ’(’ ’spl:hasData’
DataExpression ’)’
Purpose $\mathbf{\mathrel{\mathop{:}}=}$’ObjectSomeValueFrom’ ’(’
’spl:hasPurpose’ PurposeExpression ’)’
Processing $\mathbf{\mathrel{\mathop{:}}=}$’ObjectSomeValueFrom’ ’(’
’spl:hasProcessing’ ProcessingExpression ’)’
Recipients $\mathbf{\mathrel{\mathop{:}}=}$’ObjectSomeValueFrom’ ’(’
’spl:hasRecipient’ RecipientExpression ’)’
Storage $\mathbf{\mathrel{\mathop{:}}=}$’ObjectSomeValueFrom’ ’(’
’spl:hasStorage’ StorageExpression ’)’
DataExpression $\mathbf{\mathrel{\mathop{:}}=}$’spl:AnyData’ $\;\mid\;$
DataVocabExpression
PurposeExpression $\mathbf{\mathrel{\mathop{:}}=}$’spl:AnyPurpose’ $\;\mid\;$
PurposeVocabExpression
ProcessingExpression $\mathbf{\mathrel{\mathop{:}}=}$’spl:AnyProcessing’
$\;\mid\;$ ProcessingVocabExpression
RecipientsExpression $\mathbf{\mathrel{\mathop{:}}=}$’spl:AnyRecipient’
$\;\mid\;$ ’spl:Null’ $\;\mid\;$ RecipientVocabExpression
StorageExpression $\mathbf{\mathrel{\mathop{:}}=}$’spl:AnyStorage’ $\;\mid\;$
’spl:Null’ $\;\mid\;$
’ObjectIntersectionOf’ ’(’ Location Duration ’)’
Location $\mathbf{\mathrel{\mathop{:}}=}$’ObjectSomeValueFrom’ ’(’
’spl:hasLocation’ LocationExpression ’)’
Duration $\mathbf{\mathrel{\mathop{:}}=}$’ObjectSomeValueFrom’ ’(’
’spl:hasDuration’ DurationExpression ’)’
$\;\mid\;$ ’DataSomeValueFrom’ ’(’ ’spl:durationInDays’ IntervalExpression ’)’
LocationExpression $\mathbf{\mathrel{\mathop{:}}=}$’spl:AnyLocation’
$\;\mid\;$ LocationVocabExpression
DurationExpression $\mathbf{\mathrel{\mathop{:}}=}$’spl:AnyDuration’
$\;\mid\;$ DurationVocabExpression
IntervalExpression $\mathbf{\mathrel{\mathop{:}}=}$’DatatypeRestriction’ ’(’
’xsd:integer’ LowerBound UpperBound ’)’
LowerBound $\mathbf{\mathrel{\mathop{:}}=}$’xsd:minInclusive’ IntegerLiteral
UpperBound $\mathbf{\mathrel{\mathop{:}}=}$’xsd:maxInclusive’ IntegerLiteral
IntegerLiteral $\mathbf{\mathrel{\mathop{:}}=}$ stringOfDigits ’^^’
’xsd:integer’
stringOfDigits $\mathbf{\mathrel{\mathop{:}}=}$ a sequence of digits enclosed
in a pair of ” (U+22)

###  3.2 Compliance Checking

Internally, SPECIAL’s components encode also policies and the entries of the
transparency ledger with a fragment (profile) of OWL2 called $\mathcal{PL}$
(policy logic) Bonatti (2018). The adoption of a logic-based description
language has manifold reasons. First, it has a clean, unambiguous semantics,
that is a must for policy languages. A formal approach brings the following
advantages:

  * •

strong correctness and completeness guarantees on the algorithms for
permission checking and compliance checking;

  * •

the mutual coherence of the different reasoning tasks related to policies,
such as policy validation, permission checking, compliance checking, and
explanations (cf. tasks T1–T4 and the subsequent paragraph);

  * •

correct usage after data is transferred to other controllers (i.e.
interoperability). When it comes to so-called _sticky policies_ Pearson and
Mont (2011), that constitute a sort of a license that applies to the data
released to third parties, it is essential that all parties understand the
sticky policy in the same way.

Policies are modeled as OWL2 _classes_. If the policy describes a controller’s
activity, then its instances represent all the operations that the controller
may possibly execute. If the policy describes consent, then its instances
represent all the operations permitted by the data subject. A description of
(part of) the controller’s activity – called _business policy_ in SPECIAL
(possibly represented as a _transparency log entry_) – _complies_ with a
consent policy if the former is a subclass of the latter, that is, all the
possible operations described by the business policies are also permitted by
the given consent.

###### Example 2

Consider again Example 1. The JSON-like representation used there can be
directly mapped onto an OWL2 class `ObjectUnionOf(`$P_{1}\ P_{2}$`)`, where
$P_{2}$ is444We omit $P_{1}$ due to space limitations; the reader may easily
derive it by analogy with the above example.:

    ObjectIntersectionOf(
      ObjectSomeValueFrom(
        has_purpose SocialNetworking )
      ObjectSomeValueFrom(
        has_data LocationData)
      ObjectSomeValueFrom(
        has_processing Transfer)
      ObjectSomeValueFrom(
        has_recipient DataSubjFriends)
      ObjectSomeValueFrom(
        has_storage ObjectIntersectionOf(
          ObjectSomeValueFrom(has_location: EU)
          DataSomeValueFrom(has_duration
            DatatypeRestriction(xsd:integer
              xsd:minInclusive "365"^^xsd:integer
              xsd:maxInclusive "1825"^^xsd:integer
    )))

In order to check whether a business policy $BP$ (encoded as an OWL2 class)
complies with the above policy one should check whether the former is a
subclass of the latter, that is, whether:

`SubClassOf(`$BP$ `ObjectUnionOf(`$P_{1}\ P_{2}$`))`

is a logical consequence of the ontology that defines SPECIAL’s vocabularies.

##  4 Business Processes Compliance Checking

Figure 2: SPECIAL’s Business Policy Language Grammar

BusinessPolicy $\mathbf{\mathrel{\mathop{:}}=}$ BasicBP $\;\mid\;$
’ObjectUnionOf’ ’(’ BasicBP { BasicBP }* ’)’
BasicBP $\mathbf{\mathrel{\mathop{:}}=}$’ObjectIntersectionOf’ ’(’ Data
Purpose Processing Recipients Storage {Duty}* {LegalBasis} ’)’
Data $\mathbf{\mathrel{\mathop{:}}=}$ see _Section_ 3
Purpose $\mathbf{\mathrel{\mathop{:}}=}$ see _Section_ 3
Processing $\mathbf{\mathrel{\mathop{:}}=}$ see _Section_ 3
Recipients $\mathbf{\mathrel{\mathop{:}}=}$ see _Section_ 3
Storage $\mathbf{\mathrel{\mathop{:}}=}$ see _Section_ 3
Duty $\mathbf{\mathrel{\mathop{:}}=}$’ObjectSomeValuesFrom’ ’(’ ’sbpl:hasDuty’
DutyExpression ’)’
DutyExpression $\mathbf{\mathrel{\mathop{:}}=}$’sbpl:AnyDuty’ $\;\mid\;$
DutyVocabExpression
LegalBasis $\mathbf{\mathrel{\mathop{:}}=}$’ObjectSomeValuesFrom’ ’(’
’sbpl:hasLegalBasis LegalBasisVocabExpression ’)’

Beyond consent, the GDPR defines obligations that apply to the data
controllers / processors internal systems and processes. Here are two
examples:

  * •

whenever the data controller operates on personal data, it must _acquire
explicit consent_ from the involved data subjects, unless the purpose of data
processing falls within a set of exceptional cases (e.g. the processing is
required by law); cf. Article 6.1, (b)–(f);

  * •

whenever data are transferred to a third country whose data protection
regulations do not match the EU requirements, alternative guarantees must be
provided, e.g. in the form of company regulations called _binding corporate
rules_ , cf. Article 47 and, more generally, GDPR Chapter V (Transfer Of
Personal Data To Third Countries Or International Organisations).

Moreover, and differently from the above examples, the GDPR sets obligations
that are not directly related to the controller’s business processes, such as
the requirement that data subjects have the right to _access, rectify, and
delete_ their personal data. In order to fulfill such obligations, data
controllers have to set up suitable processes. Last but not least, it is
useful to label the controller/processors processes with the legal basis for
the processing; this helps in assessing and demonstrating the lawfulness of
data processing activities. For automated compliance checking descriptions of
internal systems and processes should be adequately formalized in a machine-
understandable way; moreover, the formalization should represent accurately
the real processes, in order to make the automated compliance verification
reliable.

###  4.1 Encoding Business Processes as Policies

In SPECIAL, we address a concrete setting in which a partial and abstract
description of processes is available. Each process description is shaped like
a _formalized business policy_ consisting of the following set of features:

  * •

the file(s) to be processed;

  * •

the software that carries out the processing;

  * •

the purpose of the processing;

  * •

the entities that can access the results of the processing;

  * •

the details of where the results are stored and for how long;

  * •

_the obligations that are fulfilled while (or before) carrying out the
processing;_

  * •

_the legal basis of the processing._

It is not hard to see that the first five elements in the above list match
SPECIAL’s usage policy language (UPL) introduced in _Section_ 3. As far as the
above elements are concerned, the only difference between UPL expressions and
a business policy is the granularity of attribute values. For example, the
involved data (specified in the first element of the above list) are not
expressed as a general, content-oriented category, but rather as a concrete
set of data sources or data items. Such objects can be modeled as instances or
subclasses of the general data categories illustrated in _Section_ 3, thereby
creating a link between digital artifacts and usage policies. Similar
considerations hold for the other attributes:

  * •

processing is not necessarily described in the abstract terms adopted by the
processing vocabulary introduced in _Section_ 3; in a business policy, this
can be specified by naming concrete software procedures;

  * •

the purpose of data processing may be directly related to the data
controller’s mission and products;

  * •

recipients may consist of a concrete list of legal and/or physical persons, as
opposed to general categories such as Ours or ThirdParty;

  * •

storage may be specified by a list of specific data repositories, at the level
of files and hosts.

With this level of granularity, specific authorizations can be derived from
the business policy, for example:

> The indicated software procedure can read the indicated data sources. The
> results can be written in the specified repositories. The specified
> recipients can read the repositories…

This methodology for generating authorizations fosters a close correspondence
between the business policy and the actual behavior of the data controller’s
systems and processes.

The attribute encoding obligations is not part of usage policies. It plays a
dual role, representing:

  * •

preconditions authorizations specified by the business policy, e.g. if the
obligation is something like getValidConsent then the derived authorizations
is a _rule_ like _the specified software can read the data sources if consent
has been given_ ;

  * •

obligation assertions (under human responsibility) that the data controller
has set up _processes for fulfilling the indicated obligations_ – e.g. a
process to obtain consent from the data subjects – which is relevant to
checking compliance with the GDPR.

###  4.2 Business Policies in OWL2

A basic business policy is simply a usage policy (as in _Section_ 3) extended
with zero or more obligations, and a legal basis, encoded with attributes
hasDuty and hasLegalBasis, for example the following policy associates the
collection of personal demographic information to the obligations to get
consent and let the data subject exercise her rights:

ObjectIntersectionOf( ObjectSomeValuesFrom (spl:hasData svd:Demographic)
ObjectSomeValuesFrom (spl:hasProcessing svpr:Collect) ObjectSomeValuesFrom
(spl:hasPurpose svpu:Account) ObjectSomeValuesFrom (spl:hasRecipient svr:Ours)
ObjectSomeValuesFrom (spl:hasStorage ObjectIntersectionOf( spl:hasLocation
svl:OurServers spl:hasDuration svdu:Indefinitely ) ) ObjectSomeValuesFrom
(sbpl:hasDuty getValidConsent) ObjectSomeValuesFrom (sbpl:hasDuty
getAccessReqs) ObjectSomeValuesFrom (sbpl:hasDuty getRectifyReqs)
ObjectSomeValuesFrom (sbpl:hasDuty getDeleteReqs) ObjectSomeValuesFrom
(sbpl:hasLegalBasis A6-1-a-explicit-consent) )

Similarly to usage policies, _general_ business policies can be composed by
enclosing several basic business policies inside the ObjectUnionOf operator of
OWL2. The syntax and the logical semantics of SPECIAL’s Business Policy
Language are specified in Figure 2. The values for attributes
DutyVocabExpression and LegalBasisVocabExpression are specified in DPVCG’s
vocabularies.

###  4.3 Partial Encoding of the GDPR in OWL2

The GDPR cannot be fully axomatized due to the usual difficulties that arise
in axiomatizing legal text (especially the frequent use of subjective terms as
highlighted in _Section_ 2). However it is possible to encode some constraints
that should hold over the different attributes of a business policy. At the
top level, the formalization is organized as follows:

ObjectUnionOf(
ObjectIntersectionOf(
Chap2_LawfulProcessing
Chap3_RightsOfDataSubjects
Chap4_ControllerAndProcessorObligations
Chap5_DataTransfer
)
Chap9_Derogations
)

Informally, the above expression says that either the requirements of GDPR
Chapters 1–5 are satisfied, or some of the derogations provided by GDPR
Chapter 9 should apply. In turn, each of the above terms is equivalent to a
compound OWL2 class that captures more details from the regulation. Here we
illustrate part of the formalization of GDPR Chapter 2 for an example.
Chap2_LawfulProcessing is equivalent to the following expression:

ObjectUnionOf(
Art6_LawfulProcessing
Art9_SensitiveData
Art10_CriminalData
)

The above three conditions apply, respectively, to non-sensitive personal
data, sensitive data, and criminal data. At least one of the three conditions
should be satisfied. In turn, Art6_LawfulProcessing is defined as:

ObjectUnionOf(
ObjectSomeValuesFrom(spl:hasData
SensitiveData_as_per_Art9
)
ObjectSomeValuesFrom(spl:hasData
CriminalConvictionData_as_per_Art10
)
Art6_1_LegalBasis
Art6_4_CompatiblePurpose
)
)

Roughly speaking, the above union represents an implication in disjunctive
normal form, and should be read like this: if the data involved in the
processing is neither sensitive nor criminal conviction data, then either the
fundamental legal bases of Art. 6(1) apply, or the processing is compatible
with the original purpose for collecting the data as per Art. 6(4). In order
to capture this meaning, class Art6_1 is defined as:

ObjectSomeValuesFrom(hasLegalBasis
ObjectUnionOf(
Art6_1_a_Consent
Art6_1_b_Contract
Art6_1_c_LegalObligation
Art6_1_d_VitalInterest
Art6_1_e_PublicInterest
Art6_1_f_LegitimateInterest
)
)

Roughly speaking, this definition means that a business policy satisfies the
requirements of Art. 6(1) if it contains a clause

ObjectSomeValueFrom( hasLegalBasis $X$ )

where $X$ is some of the above classes corresponding to points _a–f_ of Art.
6(1). In practice, this means that a human expert has to pick an appropriate
legal basis for each business policy. Similarly, the formalization of Article
9 applies to sensitive data categories only, and requires a legal basis from a
different list. So the term SensitiveData_as_per_Art9 is equivalent to:

ObjectUnionOf(
ObjectSomeValuesFrom(spl:hasData
ObjectComplementOf(SensitiveData_as_per_Art9)
)
ObjectSomeValuesFrom(hasLegalBasis
ObjectUnionOf(
Art9_2_a_Consent
Art9_2_b_EmploymentAndSocialSecurity
Art9_2_c_VitalInterest
Art9_2_d_LegitimateActivitiesOfAssociations
Art9_2_e_PublicData
Art9_2_f_Juducial
Art9_2_g_PublicInteres
Art9_2_h_PreventiveOrOccupationalMedicine
Art9_2_i_PublicHealth
Art9_2_j_ArchivingResearchStatistics
)
)
)

The rest of the regulation is formalized with a similar approach.

###  4.4 Compliance Checking

Let us now make an example of compliance checking of a business policy w.r.t.
the above axiomatization. Consider the following business policy:

ObjectIntersectionOf(
ObjectSomeValuesFrom( hasData Religion )
ObjectSomeValuesFrom( hasProcessing Collect )
ObjectSomeValuesFrom( hasPurpose
PersonalisedBenefits )
ObjectSomeValuesFrom( hasStorage
ObjectSomeValuesFrom( hasLocation EU ))
ObjectSomeValuesFrom( hasRecipient
DataProcessor )
ObjectSomeValuesFrom( hasDuty
Art12-22_SubjectRights )
ObjectSomeValuesFrom( hasDuty
Art32-37_Obligations )
ObjectSomeValuesFrom( hasLegalBasis
Art6_1_a_Consent )
)

This policy is not a subclass of the formalized GDPR (hence it does not pass
the compliance check) because Religion is classified as sensitive data (it is
a subclass of SensitiveData_as_per_Art9). Then the business policy is not a
subclass of Art9_SensitiveData, because the legal basis is not among the
required list. Moreover, the business policy is not covered by the derogations
provided by GDPR Chapter 9 (details are omitted here). As a consequence, the
business policy does not satisfy the conditions specified by
Chap2_LawfulProcessing. Note that this kind of compliance checking is able to
verify the coherency of the different parts of a business policy.

If Religion was replaced by any non-sensitive data category such as Location,
then the policy would be compliant because it would be a subclass of
Art6_LawfulProcessing. This satisfies the condition called
Chap2_LawfulProcessing. The hasDuty attributes of the business policy suffice
to satisfy Chap3_RightsOfDataSubjects and Chap4
ControllerAndProcessorObligations. Chap5_DataTransfer would also be satisfied
since the processing does not involve any transfers outside the EU.

##  5 Our Automated Compliance Checking Algorithm

Business policies (that describe the processing of each of the controller’s
processes) are not only needed to fulfill the requirements of Article 30. They
can also be used to check whether a running process complies with the
available consent, as a sort of access control system. Several implementation
strategies are possible, depending on the controller’s system architecture; to
fix ideas, the reader may consider the following generic approach: Each of the
controller’s processes is labeled with a corresponding business policy that
describes it, and before processing a piece of data, the business policy is
compared with the data subject’s consent to check whether the operation is
permitted.

In general, such compliance checks occur frequently enough to call for a
scalable implementation. Consider, for example, a telecom provider that
collects location information to offer location-based services. Locations
cannot be stored without a legal basis, such as law requirements or consent –
not even temporarily, while a batch process selects the parts that can be
legally kept. So compliance checking needs to be executed on the fly. In order
to estimate the amount of compliance checks involved, consider that the events
produced by the provider’s base stations are approximately 15000 per second;
the probing records of wi-fi networks are about 850 millions per day.

In order to meet such performance requirements, SPECIAL has developed ad-hoc
reasoning algorithms for $\mathcal{PL}$ Bonatti (2018), that leverage
$\mathcal{PL}$’s simplicity to achieve unprecedented reasoning speed.
Compliance checking is split into two phases: first, business policies are
normalized and closed under the axioms contained in the vocabularies; in the
second phase, business policies are compared with consent policies with a
_structural subsumption_ algorithm. We have just completed the evaluation of a
sequential Java implementation of those algorithms, called PLR. We chose Java
to facilitate the comparison with other engines, by exploiting the standard
OWL APIs, and we refrained to apply parallelization techniques in order to
assess the properties of the basic algorithms. Before discussing more
performant implementation options, we report the results for PLR.

PLR can pre-compute the first phase, since the business policies are known in
advance and are typically persistent. So the runtime cost is reduced to
structural subsumption. In this way, on the test cases derived from SPECIAL’s
use cases (cf. Table 1), the performance we achieve, respectively, is
$150\mu$sec and $190\mu$sec per compliance check, using the following system:

processor: | Intel Xeon Silver 4110
---|---
cores: | 8
cache: | 11M
RAM: | 198 GB
OS: | Ubuntu 18.4
JVM: | 1.8.0_181
heap: | 32 GB (actually used: less than 700 MB).

This means that PLR alone can execute about 6000 compliance checks per second
and more than 518 million checks per day, that is, 60% of wi-fi probing events
and 40% of base station events.

| Pilot 1 | Pilot 2
---|---|---
Ontology |  |
inclusions | 186 | 186
disjoint class axioms | 11 | 11
property range axioms | 10 | 10
functional properties | 8 | 8
classification hierarchy height | 4 | 4
Business policies |  |
# generated policies | 120 | 100
avg. simple pol. per full pol. | 2.71 | 2.39
Consent policies |  |
# generated policies | 12,000 | 10,000
avg. simple pol. per full pol. | 3.77 | 3.42
Test cases |  |
# compliance checks | 12,000 | 10,000
Table 1: Test cases derived from SPECIAL’s pilots

In order to raise performance up to the required levels, one can re-engineer
PLR using a language more performant than Java, and/or parallelize processing
by means of big data architectures. Compliance checking is particularly well
suited to parallelization, since each test is independent from the others and
no synchronization is required. Additionally, the investigation of
parallelization within PLR’s algorithms is under investigation.

##  6 Related Work

From a GDPR compliance perspective, there exist several compliance tools (cf.
Information Commissioner’s Office UK(2017) (ICO); Microsoft Trust Center
(2017); Nymity ; Agarwal et al. (2018)) that enable companies to assess the
compliance of applications and business processes via predefined
questionnaires.

There is also a large body of work on legal knowledge representation
(cf.Bartolini et al. (2015); Pandit et al. (2018)) and reasoning (cf.
Palmirani et al. (2011); Athan et al. (2013); Governatori et al. (2016); Lam
and Hashmi (2019)). From a representation perspective, Bartolini et al. (2015)
and Pandit et al. (2018) propose ontologies that can be used to model data
protection requirements. While, Palmirani et al. (2011) and Athan et al.
(2013) demonstrate how LegalRuleML can be used to specify legal norms. The
work by Lam and Hashmi (2019) and Governatori et al. (2016) also builds upon
LegalRuleML, however the focus is more on ensuring business process
compliance.

Both rule languages and OWL2 have already been used as policy languages; a
non-exhaustive list is Woo and Lam (1993); Jajodia et al. (2001); Uszok et al.
(2003); Kagal et al. (2003); Bonatti et al. (2010). As noted in Bonatti
(2010), the advantage of OWL2 – hence description logics – is that all the
main policy-reasoning tasks are decidable (and tractable if policies can be
expressed with OWL2 profiles), while compliance checking is undecidable in
rule languages, or at least intractable – in the absence of recursion –
because it can be reduced to datalog query containment. So an OWL2-based
policy language is a natural choice in a project like SPECIAL, where policy
comparison is the predominant task. Among the aforementioned languages, both
Rei and Protune Kagal et al. (2003); Bonatti et al. (2010) support logic
program rules, which make them unsuitable to SPECIAL’s purposes. KAoS Uszok et
al. (2003) is based on a description logic that, in general, is not tractable,
and supports role-value maps – a construct that easily makes reasoning
undecidable (see Baader et al. (2003), Chap. 5). The papers on KAoS do not
discuss how to address this issue.

P3P’s privacy policies – that are encoded in XML – and simple $\mathcal{PL}$
policies have a similar structure: the tag $\mathtt{STATEMENT}$ contains tags
$\mathtt{PURPOSE}$, $\mathtt{RECIPIENT}$, $\mathtt{RETENTION}$, and
$\mathtt{DATA\mbox{-}GROUP}$, that correspond to the analogous properties of
SPECIAL’s usage policies. Only the information on the location of data is
missing. The tag $\mathtt{STATEMENT}$ is included in a larger context that
adds information about the controller (tag $\mathtt{ENTITY}$) and about the
space of web resources covered by the policy (through so-called _policy
reference files_). Such additional pieces of information can be directly
encoded with simple $\mathcal{PL}$ concepts.

There exist several well-engineered reasoners for OWL2 and its profiles.
Hermit Glimm et al. (2014) is a general reasoner for OWL2. Over the test cases
inspired by SPECIAL’s use cases, it takes 3.67 ms and 3.96 ms per compliance
check, respectively, that is, over 20 times longer than PLR. ELK Kazakov et
al. (2014) is a specialized polynomial-time reasoner for the OWL2-EL profile.
It does not support functional roles, nor the interval constraints used to
model storage duration, therefore it cannot be used to reason on the
$\mathcal{PL}$ profile. Konclude Steigmiller et al. (2014) is a highly
optimized reasoner with “pay-as-you-go” strategies (i.e. it becomes more
efficient on less complex profiles of OWL2). Konclude is designed for
classification, and is currently not optimized for subsumption tests (i.e. the
reasoning task underlying compliance checks). Consequently, it turns out to be
slower than Hermit on our test cases.

##  7 Conclusion and Future Work

The overarching goal of the SPECIAL project is to develop tools and
technologies that enable data controllers and processors to comply with
personal data processing obligations specified in the GDPR. In this paper, we
presented the SPECIAL policy language and discussed how it can be used to
encode consent, business policies, and regulatory obligations. In addition we
described the SPECIAL approaches to GDPR compliance checking and presented the
results of our initial performance evaluation.

Ongoing/future work includes: the optimisation of the existing compliance
checking algorithm to cater for automated compliance checking for a broader
set of legislative requirements; and the development of an algebra that can be
used to combine multiple policies, for instance where there is a need to
aggregate data from multiple data sources.

## Acknowledgment

This research is funded by the European Union’s Horizon 2020 research and
innovation programme under grant agreement N. 731601. The authors are grateful
to all of SPECIAL’s partners; without their contribution this project and its
results would not have been possible.

## References

  * Agarwal et al. [2018] S. Agarwal, S. Steyskal, F. Antunovic, and S. Kirrane.  Legislative compliance assessment: Framework, model and gdpr instantiation.  In _Annual Privacy Forum_ , pages 131–149. Springer, 2018.
  * Athan et al. [2013] T. Athan, H. Boley, G. Governatori, M. Palmirani, A. Paschke, and A. Z. Wyner.  Oasis LegalRuleML.  In _ICAIL_ , volume 13, pages 3–12, 2013.
  * Baader et al. [2003] F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, and P. F. Patel-Schneider, editors.  _The Description Logic Handbook: Theory, Implementation, and Applications_ , 2003. Cambridge University Press.  ISBN 0-521-78176-0.
  * Bartolini et al. [2015] C. Bartolini, R. Muthuri, and C. Santos.  Using ontologies to model data protection requirements in workflows.  In _JSAI International Symposium on Artificial Intelligence_ , 2015\.
  * Bonatti [2010] P. A. Bonatti.  Datalog for security, privacy and trust.  In _Datalog Reloaded - First International Workshop, Datalog 2010, Oxford, UK, March 16-19, 2010. Revised Selected Papers_ , pages 21–36, 2010\.  doi: 10.1007/978-3-642-24206-9˙2.
  * Bonatti [2018] P. A. Bonatti.  Fast compliance checking in an OWL2 fragment.  In J. Lang, editor, _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden._ , pages 1746–1752. ijcai.org, 2018.  ISBN 978-0-9992411-2-7.  doi: 10.24963/ijcai.2018/241.
  * Bonatti et al. [2010] P. A. Bonatti, J. L. D. Coi, D. Olmedilla, and L. Sauro.  A rule-based trust negotiation system.  _IEEE Trans. Knowl. Data Eng._ , 22(11):1507–1520, 2010.  doi: 10.1109/TKDE.2010.83.
  * Glimm et al. [2014] B. Glimm, I. Horrocks, B. Motik, G. Stoilos, and Z. Wang.  Hermit: An OWL 2 reasoner.  _J. Autom. Reasoning_ , 53(3):245–269, 2014.  doi: 10.1007/s10817-014-9305-1.
  * Governatori et al. [2016] G. Governatori, M. Hashmi, H.-P. Lam, S. Villata, and M. Palmirani.  Semantic business process regulatory compliance checking using LegalRuleML.  In _European Knowledge Acquisition Workshop_ , 2016.
  * Information Commissioner’s Office UK(2017) [ICO] Information Commissioner’s Office (ICO) UK.  Getting ready for the GDPR, 2017.  URL https://ico.org.uk/for-organisations/resources-and-support/data-protection-self-assessment/getting-ready-for-the-gdpr/.
  * Jajodia et al. [2001] S. Jajodia, P. Samarati, M. L. Sapino, and V. S. Subrahmanian.  Flexible support for multiple access control policies.  _ACM Trans. Database Syst._ , 26(2):214–260, 2001.
  * Kagal et al. [2003] L. Kagal, T. W. Finin, and A. Joshi.  A policy language for a pervasive computing environment.  In _4th IEEE International Workshop on Policies for Distributed Systems and Networks (POLICY)_ , pages 63–. IEEE Computer Society, June 2003.  ISBN 0-7695-1933-4.
  * Kazakov et al. [2014] Y. Kazakov, M. Krötzsch, and F. Simancik.  The incredible ELK - from polynomial procedures to efficient reasoning with EL ontologies.  _J. Autom. Reasoning_ , 53(1):1–61, 2014.  doi: 10.1007/s10817-013-9296-3.
  * Lam and Hashmi [2019] H.-P. Lam and M. Hashmi.  Enabling reasoning with LegalRuleML.  _Theory and Practice of Logic Programming_ , 19(1):1–26, 2019.
  * Microsoft Trust Center [2017] Microsoft Trust Center.  Detailed GDPR Assessment, 2017.  URL http://aka.ms/gdprdetailedassessment.
  * [16] Nymity.  GDPR Compliance Toolkit.  URL https://www.nymity.com/gdpr-toolkit.aspx.
  * Palmirani et al. [2011] M. Palmirani, G. Governatori, A. Rotolo, S. Tabet, H. Boley, and A. Paschke.  LegalRuleML: XML-based rules and norms.  In _International Workshop on Rules and Rule Markup Languages for the Semantic Web_ , pages 298–312, 2011.
  * Pandit et al. [2018] H. J. Pandit, K. Fatema, D. O’Sullivan, and D. Lewis.  Gdprtext-gdpr as a linked data resource.  In _European Semantic Web Conference_ , pages 481–495, 2018.
  * Pandit et al. [2019] H. J. Pandit, A. Polleres, B. Bos, R. Brennan, B. P. Bruegger, F. J. Ekaputra, J. D. Fernández, R. G. Hamed, E. Kiesling, M. Lizar, E. Schlehahn, S. Steyskal, and R. Wenning.  Creating a vocabulary for data privacy - the first-year report of data privacy vocabularies and controls community group (DPVCG).  In _On the Move to Meaningful Internet Systems: OTM 2019 Conferences - Confederated International Conferences: CoopIS, ODBASE, C &TC 2019, Rhodes, Greece, October 21-25, 2019, Proceedings_, pages 714–730, 2019\.
  * Pearson and Mont [2011] S. Pearson and M. C. Mont.  Sticky policies: An approach for managing privacy across multiple parties.  _IEEE Computer_ , 44(9):60–68, 2011.  doi: 10.1109/MC.2011.225.
  * Steigmiller et al. [2014] A. Steigmiller, T. Liebig, and B. Glimm.  Konclude: System description.  _J. Web Semant._ , 27-28:78–85, 2014.  doi: 10.1016/j.websem.2014.06.003.
  * Uszok et al. [2003] A. Uszok, J. M. Bradshaw, R. Jeffers, N. Suri, P. J. Hayes, M. R. Breedy, L. Bunch, M. Johnson, S. Kulkarni, and J. Lott.  KAoS policy and domain services: Towards a description-logic approach to policy representation, deconfliction, and enforcement.  In _4th IEEE International Workshop on Policies for Distributed Systems and Networks (POLICY)_ , pages 93–96. IEEE Computer Society, June 2003\.  ISBN 0-7695-1933-4.
  * Woo and Lam [1993] T. Y. C. Woo and S. S. Lam.  Authorizations in distributed systems: A new approach.  _Journal of Computer Security_ , 2(2-3):107–136, 1993.  doi: 10.3233/JCS-1993-22-304.