# Implementation of An Automated Learning System for Non-experts

Phoenix X. Huang Lighthouse  Zhiwei Zhao Lighthouse  Chao Liu Lighthouse
Jingyi Liu Lighthouse  Wenze Hu Lighthouse  Xiaoyu Wang Lighthouse

###### Abstract

Automated machine learning systems for non-experts could be critical for
industries to adopt artificial intelligence to their own applications. This
paper detailed the engineering system implementation of an automated machine
learning system called YMIR, which completely relies on graphical interface to
interact with users. After importing training/validation data into the system,
a user without AI knowledge can label the data, train models, perform data
mining and evaluation by simply clicking buttons. The paper described: 1) Open
implementation of model training and inference through docker containers. 2)
Implementation of task and resource management. 3) Integration of Labeling
software. 4) Implementation of HCI (Human Computer Interaction) with a rebuilt
collaborative development paradigm. We also provide subsequent case study on
training models with the system. We hope this paper can facilitate the
prosperity of our automated machine learning community from industry
application perspective. The code of the system has already been released to
GitHub111https://github.com/industryessentials/ymir.

##  1 Introduction

Many AutoML techniques such as NAS and HPO have greatly simplified the task of
finding the best models and hyper parameters for machine learning problems,
and contribute to the wide adoption of ML in various fields. However, in
industrial settings, modeling is only one of many factors which affect the
efficiency and simplicity of a machine learning development process. A
systematic approach that manages and automates the entire pipeline could be a
key to land AutoML into in more application areas.

In ready to use AutoML systems such as Google Cloud AutoML, Amazon SageMaker
Autopilot etc. , a model development pipeline is simplified to three steps:
upload data, train model and deployment. While this simplified process
achieves the goal of producing models, in actual use cases, the model
development processes are almost always iterative, either because the raw data
arrives in batches, or the labeling cost is too prohibitive that labeling has
to be done in batches. In these settings, the time spent repeating non-
training steps is usually much longer than training the models, rendering an
automated pipeline more valuable than only automating the model training step
itself.

YMIR222YMIR denotes You Mine In Recursive is a machine learning platform that
simplifies and automates the production grade machine learning processes in
industrial settings. The system enables non-expert users to develop AI models
through a no-code style GUI. To achieve this goal, YMIR defines its own
generic model training and inference task protocols to support different
algorithm implementations for various machine learning problems, its own task
management and resource allocation framework to better organize and track
machine learning tasks for multiple parallel projects, as well as its own GUI
to emphasis an active learning based iterative machine learning development
pipeline. Our case study in appendix shows that this platform can be used by
non-experts to train and iterate models for production purposes, which helps
wide adoption of AI to new application fields.

It is noted that while the high-level concept design of YMIR is introduced in
[Huang et al., 2021], this paper emphasis on the engineering design principles
as well as implementation details. The appendix includes case studies showing
its effectiveness in speeding up the AI model development process.

##  2 Industrial AI Model Development Process

YMIR is developed under the data-centric principle with focuses on efficient
model and data iterations. As is shown in Figure 1, YMIR defines an iterative
model development process as following steps:

Data: $Data_{superset}$ ;

/* The whole available data */

Result: Application Specific Model $M_{o}$

$Acc_{T}\leftarrow A$ ;

/* Target model accuracy */

$M_{0}\leftarrow$ Empty model or pretrained model ;

$D_{0}\leftarrow$ Empty, $Acc_{0}\leftarrow 0$, $i\leftarrow 0$ ;

/* Initialize data, accuracy, iteration index */

while  _$Acc_{i}\leq Acc_{T}$ ;_

__ /* Continue if the model accuracy is not sufficient */

do

_ _if  _User Interrupts The Process ;_

__ /* Terminated by user */

then

$M_{o}\leftarrow M_{i}$;

Break;

else

$d_{i}\leftarrow$ Data mining output with $M_{i}$ and $Data_{superset}$ if
$i>0$, otherwise Initial Data ;

Label $d_{i}$ ;

/* Label the mined data */

$D_{i+1}\leftarrow D_{i}\cup d_{i}$ ;

/* Update training data */

$M_{i+1}\leftarrow$ Model trained on $D_{i+1}$ ;

/* Update model */

$Acc_{i+1}\leftarrow$ Evaluate $M_{i+1}$ ;

/* Evaluate model */

end if

$M_{o}\leftarrow M_{i+1}$, $i\leftarrow i+1$ ;

/* Update model */

end while

Figure 1: Model development process in YMIR system. Left: In algorithm format.
Right: In the diagram format.

  1. 1.

Solution Design:  This stage focuses on converting the business needs into an
existing type of modeling problem. Taking computer vision as an example, the
modeling problem could be image classification, object detection,
segmentation, or a combination of multiple techniques.

  2. 2.

Data Preparation:  Data preparation mainly refers to the process of collecting
and pre-processing data for a target technical solution. Data collection is
usually performed iteratively until the resulting technical solution meets the
application requirements.

  3. 3.

Model Training: Commonly known as "modeling", this is the step of exploring
and analyzing prepared data through analytical tools, methods and techniques
to discover input-output relationships and internal connections to inform
decisions for business purposes. The result of this process is usually one or
more machine learning models. The model training process is also iterative
followed by data updates, until the model accuracy meets application
requirements.

  4. 4.

Model Evaluation: This step evaluates performances of the models obtained from
the model training step. Different from only using key metrics such as
accuracy or sensitivity as diagnostic measures, which are usually computed on
validation data while training the model, this process may involve more in-
depth analysis of the results on testing datasets, such as model bias or
metrics on sub-groups of the validation/testing sets.

  5. 5.

Data Mining: This stage focuses on finding the best data that improves the
current models. On many applications this is a necessary step because the
modeled events are usually rare events in the source dataset, and the cost of
blindly labeling all the data could be prohibitive.

  6. 6.

Model Deployment: Trained and evaluated model needs to be applied to
production data or newly acquired data to generate predictions which provide
the high-value information for business purpose. The model usually is usually
optimized in terms of computational cost in this step, to save the eventual
cost of running them on real data.

Processes $2$ through $5$ are repeated for improved model accuracy, while
process $1$ and $6$ are separate procedures which are typically performed
offline. In following sections, we focus on the implementation of process $2$
through $5$. Figure 1 illustrated the iteration logic in both algorithm format
and graph format for better understanding.

Figure 2: YMIR decomposed into engineering layers. YMIR-HCI guides user
operations and assists users to develop AI model more efficiently; YMIR-Web UI
provides UI controls for users to visualize/operate dataset and tasks; YMIR-
Application: this layer maintains the relationship among user/task/assets, as
well as permissions; YMIR-Controller manages task framework and tracks the
progress of individual task. The infra layer manages all infrastructure
resources, data storage solution, _etc_.

##  3 System Implementation

In YMIR, the pipeline introduced above is implemented through four key
components, which are shown in Table 1 and Figure 2: 1) YMIR-TMI implements
model related operations including training, testing and data mining. 2) YMIR-
Controller implements task and resource management. 3) YMIR-Labeling
implements data labeling and connects to data labeling services through open
interfaces. 4) YMIR-HCI implements front-end user interface for the platform.

Modules |  Function Description
---|---
YMIR-TMI |  Open design of model Training/Mining/Inference (TMI) services through docker containers. Adding a new TMI related algorithm can be achieved by replacing the corresponding docker image.
YMIR-Controller |  Implementation of task and resource management. It decomposes ML tasks into atomic operations. Resource sharing, task progress monitoring and task orchestration are done by scheduling on top of these operations.
YMIR-Labeling |  Open API for integration of data labeling softwares.
YMIR-HCI |  Design of Human Computer Interaction (HCI). The graphical interface aims at implementing a rebuilt collaborative development paradigm, which guides users through the model and data iteration process. User actions as well as operation outputs together with key metrics are recorded, which makes the process trackable. The system improves the efficiency of data iteration and model production by interactive guidance through the whole process.

Table 1: Main Engineering Components of YMIR

###  3.1 YMIR-TMI

####  3.1.1 Design Principle

The focus of the YMIR platform is on data management and process control. When
it comes to the TMI services, we decouple these services from the platform and
treat them as plug and play black boxes. While YMIR provides default TMI
dockers, users and third-party developers have the freedom to write and
integrate their own related algorithms, as long as the corresponding docker
images is compatible with the defined protocol.

YMIR interacts with TMI services in the following way:

  * •

The YMIR platform, in conjunction with the TMI services, fulfills the whole
development requirements. a. the YMIR platform extracts the metadata for TMI
services from docker images (descriptions, configurations, etc.) b. The YMIR
platform provides input data to TMI services, and collects results when those
service jobs are completed. c. The YMIR platform catches the exceptions and
errors generated during the operation of TMI services. d. The YMIR platform
collects the real-time status of TMI services (whether a service is running
normally, its progress or real-time logs, _etc_.)

  * •

A TMI service is decoupled from the YMIR platform. The service is responsible
for the correctness on the implementation of corresponding model and data
methodologies.

  * •

The YMIR platform is not aware of the internal dependencies of these services.

  * •

There is no dependency between the YMIR platform and the versions of these
services.

####  3.1.2 Implementation

Name |  Interaction |  Flow Direction |  Notes
---|---|---|---
Metadata |  When the TMI service is registered. |  YMIR reads from TMI services. |  A description of the TMI service itself, and the list of key configurable parameters.
Logs |  During the operation of the TMI instance. |  Generated by the TMI instance, read and logged by YMIR. |  The runtime logs generated by the TMI instance are only stored by YMIR and do not need to be understood.
Status Monitoring |  During the runtime of a TMI instance. |  Generated by the TMI instance (written to a location-specific file using a defined format), read by YMIR |  Monitoring information generated by the TMI instance about its latest status.
Input |  Before the TMI instance runs. |  Generated by YMIR (placed in a specific path and mounted at boot time) and read by the TMI instance |  For the training service: training set, test set, pre-trained model, service parameter profile; For mining service: model, candidate set, service parameter profile; For the inference service: model, set of images to be inferred, service parameter profile.
Output |  After the TMI instance is completed |  Generated by the TMI instance (written to a specific location using a defined format) and read by YMIR. |  For the training service: model, result parameters file; For mining service: mining result files; For inference service: inference result files.

Table 2: Summary of the data exchange between YMIR system and TMI services.

The TMI services are encapsulated into separated docker images, and the YMIR
platform follows the life-cycle described in Section 2 to invoke these
services. YMIR instantiates TMI services and interact with them following
principles described in 3.1.1. In the following we explain TMI service
registration and the service runtime.

  1. 1.

Service registration. A service is available only after it is registered in
YMIR. The availability ends when the service is logged off. For a registered
service, the user should make sure:

    1. (a)

The YMIR platform is aware of the metadata associated with this service.

    2. (b)

The docker image which implements the specific task is ready to be
instantiated.

  2. 2.

Service runtime: The system can instantiate one or more services after the
service is registered. Unless exited with errors, the respective service keeps
in the runtime until the job is finished. TMI instances in runtime period have
the following characteristics.

    1. (a)

Different TMI instances do not interfere with each other. There is no
communication between instances, either.

    2. (b)

YMIR has real-time access to the operational status of these instances.

    3. (c)

YMIR is notified when a instance finishes running or exits with errors.

Table 2 summarizes data exchange between the YMIR platform and TMI services
instances.

The life cycle of TMI services is illustrated in Fig 3. It consists of
multiple stages.

Figure 3: Overview of the TMI service life cycle.

Instantiation start-up. YMIR follows the listed steps below to start a TMI
service:

  1. 1.

The user chooses a service (docker image) to start with, and sets up necessary
configurations for the service.

    1. (a)

For the task of model training, the configuration of training sets and testing
sets is mandatory. YMIR allows users to configure their pre-trained models for
initialization if there is any.

    2. (b)

For the task of data mining or inference, only the target mining dataset or
the dataset for inference is needed.

  2. 2.

YMIR platform reads assets configured in Step 1 and hosts them in predefined
locations.

  3. 3.

The TMI instance (docker container) starts its main process, taking the
datasets, models and configuration files from predefined locations.

Instance status monitoring. When the main process of the instance starts, the
YMIR platform interacts with this instance in two ways. 1\. All standard and
error outputs generated by the instance are logged to a file. 2\. The latest
status and progress of the instance is written to a status monitoring file,
and changes to this file are logged by the YMIR platform.

End of instance. If the instance executes all operations and returns a true
value, the YMIR platform will consider it as a successful run. For these
instances, the YMIR platform stores the results and updates the status of the
tasks. If the instance exited unexpectedly or the return value is not true,
the YMIR platform marks the task as a failure and archives the intermediate
results (if any). If the user chooses to manually stop this instance during
the execution of an instance, the YMIR platform sends a docker stop command to
this instance, collects any intermediate results that may exist, and marks
this task as broken.

###  3.2 YMIR-Controller: Implementation of Task and Resource Management

In YMIR, machine learning tasks are decomposed into smaller granular atomic-
level tasks, which can be reorganized to achieve reuse of resources, progress
monitoring at a smaller granularity. Task parallelization also benefits from
the design.

####  3.2.1 Task Scheduling

The task scheduling component manages to connect a series of subtasks to
implement the task defined by the user. It supports tasks parallelization if
there are enough resources to support these tasks.

  1. 1.

Data preparation subtask. The dataset preparation stage is separated, and only
one copy of this original data of the image is kept, and the original content
of the image is calculated using sha256() as the identifier of the image,
which is reused in other tasks to avoid multiple copies of the original data,
taking up storage space and task time, etc.

  2. 2.

Dataset processing. Filtering, merging, taking intersection and merging of
datasets, etc., will generate a new dataset after completion, which can also
be reused by other tasks

  3. 3.

GPU resource allocation. When the data is processed, before using GPU
resources for training, the GPU ID used is stored from the task layer
perspective, and the GPU resources are released when the task is completed or
failed. Thus, the GPU resources are allocated in an on-demand fashion.

  4. 4.

TMI execution. TMI services run respective jobs given all related resources
are ready .

####  3.2.2 Assets Replica Management

The target speed of data caching layer for data acquisition is within 100ms.
It is organized as:

  1. 1.

Original file parsing and verification. Get the hash_id of the image content,
and support reading the corresponding PASCAL, VOC, YOLO and other common data
formats, where the hash_id is used for image de-duplication and subsequent
identification of the image. At the same time, it can support different
strategies to ignore unknown tags, abort unknown tags, etc. to provide more
information for later data analysis.

  2. 2.

Extract key information, compress and store. After the data is obtained, it
will be compressed and serialized using Protocol Buffer, and git will be
called to store it, thus compressing the storage disk space, and also allowing
to retrace the version record information.

  3. 3.

Cache the data. The hash _id is stored in an array, while other information
such as image annotation is placed in a chain table with the head pointer of
the chain table as hash _id. hash _id represents both the image itself and the
nodes of the chain table, the array can be used for fast paging, and the chain
table ensures O(1) to find the details of the image. Since the check phase has
been de-duplicated in the previous stage, there is no problem of conflict

(a) Hash ID

(b) Caching

Figure 4: (a):Each YMIR asset has a unique ID. (b) Workflow of YMIR caching.

####  3.2.3 Task progress tracking

Background The process of synchronizing task progress information through
command, application and web UI layers is implemented in actively push
mechanism. The logic of updating task progress is as follows.

  1. 1.

YMIR-TMI and YMIR-Command write task progress to monitor.txt

  2. 2.

YMIR-Monitor component polls task progress via task_monitor, and posts to
application layer.

  3. 3.

YMIR-Application layer receives task progress message, and pushes the progress
to web UI through the protocol tunnel, and displays it on the interface.

Functional design and implementation

  1. 1.

YMIR-Monitor collector in controller layer is responsible for collecting task
progress information (user-id, task-id, percent, state code, state message,
error message, timestamp, etc.) from monitor.txt

  2. 2.

YMIR-Monitor collector sends the signal of task progress that has changed
since last updated time. The dispatcher service at the app level posts this
signal to a dedicated API at a certain interval. This signal is formed by the
task id, state code, percent, etc.

  3. 3.

web clients connect to the name-space of the current user via socketio.

To post a progress message, the event dispatcher:

  1. 1.

Create a message subscription group x for the Redis stream, with only one
consumer

  2. 2.

Create an API interface to the controller to receive information about tasks
that have changed in the meantime, and put them into the Redis stream queue as
a list when they are received

  3. 3.

When the message subscription group x detects a change in the queue, it reads
all messages from it at once, groups them by user-id and task-id, finds the
latest task status corresponding to each task-id, pushes it to the namespace
corresponding to the user-id using socketio, and writes the latest task status
to the db via the API. If the write process fails, the categorized messages
are rewritten back to the queue, and if the write process is successful, the
original messages are deleted.

Web UI subscribes to the event dispatcher service for individual user messages
(connected to the namespace corresponding to the user-id) via socketio. The
received messages are displayed to web users.

###  3.3 YMIR-Labeler: Integration of Labeling Software

Similar to YMIR-TMI system, the YMIR-Labeler component is also open-designed
to support easily integration of external labeling tools. The whole life-
circle of a labeling task is described in Figure 5. It includes following
functionalities:

Figure 5: YMIR labeling task life circle.

Functionalities

  * •

Data labeling support for various vision tasks such as
classification/detection/segmentation, _etc_.

  * •

Pre-annotation using a pre-trained model to improve labeling efficiency.

  * •

Dataset synchronization between the labeling system and YMIR.

  * •

YMIR is able to distribute tasks and retrieval results from the labeling
platform.

The open design allows YMIR to use different labeling systems which may have
their own merits for a specific task. As long as the defined communication
interface is implemented, a third party labeling platform can be used by YMIR
in a plug-and-play fashion.

With an unlabeled dataset already in YMIR, the labeling task can be simply
activated by clicking the [New Annotation Task] button in YMIR’s task
management page. Users will be redirected to the annotation task creation page
to input necessary labeling configurations and instructions. Once a labeling
task is successfully created, one can check the corresponding progress by
simply visit YMIR’s task management page. YMIR is implemented to keep
communicating with the labeling software and collect all the annotation
results once the task is completed.

###  3.4 YMIR-HCI: Iteration Pipeline Centered Design.

Figure 6: YMIR System: Guided Interactive Model Development Pipeline.

Figure 6 shows the screenshot of the project page for model development. A
pipeline composed of connected buttons resembling an actual model iteration
process defined in Figure 1 (a) is put on the most prominent area of this page
(see section "Project Helmet Detection" which includes connected actionable
items such as labeling, training, data mining, _etc_.

This pipeline gives users a clear view of the steps needed for performing one
model iteration, progress of the current iteration and overall status of the
running step. While providing high level information and actionable links to
more details, this visual pipeline gives user the implication that model
iteration is an important aspect of actual ML development project. This
impression also helps inexperienced users realize that in application-oriented
ML projects, developing a high quality dataset is equally if not more
important than changing the model architectures or tuning the model training
hyper parameters.

After a step is finished successfully, YMIR will guide the user to start the
next step by highlighting the button automatically, following the logic
specified in Figure 1. The next step can also be configured to get triggered
automatically, though we notice that many users prefer to inspect the results
before proceeding to the next step.

YMIR also provides a project view page, to facilitate users develop multiple
ML projects in parallel. More screenshots of YMIR UI are listed in Appendix.

##  4 Limitation and Broader Impact

The system only supports training vision models. As a model production
application, it should not have negative social or ethic impacts.

##  5 Conclusions

This paper introduces the engineering implementations of a machine learning
system that uses a rebuilt development pipeline to involve non-experts into ML
development process. We hope this project can facilitate the prosperity of our
automated machine learning community from an industry application perspective.

## References

  * [Huang et al., 2021] Huang, P. X., Hu, W., Brendel, W., Manmohan, C., Li, L.-J., and Wang, X. (2021).  Ymir: A rapid data-centric development platform for vision applications.  In Proceedings of the Data-Centric AI Workshop at NeurIPS.

##  6 Appendix I: Case study, Developing AI models without AI Experts

This appendix presents a case study conducted with a ML modeling team that
uses YMIR to improve their efficiency on solving real world problems.

For a time span of 2 weeks, a group of 1 ML engineer and 2 data annotators
teamed up to try iterating models using YMIR. Before using YMIR, the ML
engineer usually iterates 2 models a month, each with 2 iterations. Now, the 3
people group iterated 4 models only using two weeks. On average, the ML
engineer reported significantly less time spent on iterating these models,
from 0.3 month per model to 0.05 month. The ML engineer got extra ’free’ time
by using YMIR, which were spent on developing new algorithms and planning on
new model development projects.

Figure 7: (a) Original ML dev pipeline. Most of the steps are done by ML
engineers. (b) New dev pipeline with YMIR, which enables non-experts to
develop models.

Comparison and analysis of different model development processes.

Figure 7(a) shows the regular process of algorithm development by
professionals aka ML engineers. The main operations of these engineers are
model training, visualization, optimization, and mining, all of which needs to
be done by using code. After the mining step, the selected data is handed over
to the labeling group for labeling, and the training starts again after the
mined dataset is labeled.

Disadvantages of traditional ML development workflow.

  * •

Switching between different algorithm tasks usually takes time, and when the
data is fully labeled, the algorithm staff has other work at hand to finish,
which makes the prepared data idle waiting for engineer’s availability.

  * •

Switching between different operations requires code implementation, and the
efficiency of development depends on the coding level of the specific
engineer.

  * •

The algorithm development process cannot be tracked. If many algorithms are
developed in parallel, the algorithm developer needs to manually check the
status of each task. Depending on the developer’s work style, this could be a
major loss of productivity that can be boosted by automatic tools.

Advantages of traditional ML development work flow.

  * •

High flexibility in algorithm development, allowing selection of the most
appropriate algorithm model based on project requirements.

  * •

Multiple tools can be used to tune the algorithm, such as adjusting the model
training parameters, visualizing and analyzing the model output, and adjusting
the training and labeling strategies based on the model visualization results.

  * •

Use analysis tools to monitor model training curves, identify problems early
and correct them. This may save computational resources, and avoid wasting
time on problematic datasets to produce low performing models.

Figure 7(b) shows the model development process with YMIR. It can be observed
that the majority of the operations are performed by the annotators, and the
algorithm staff only reviews the model after it is trained and then moves
his/her time on to the next task.

Advantages of using YMIR for development

  * •

Switching between tasks and operations is simple and can be done with a single
mouse click.

  * •

Data that has been annotated can immediately be used in the next step without
waiting for the ML engineer to start the job manually.

  * •

One operator can develop multiple algorithms at the same time.

  * •

Reduce the knowledge requirement of algorithm development, so that people with
no development experience can train and iterate models according to the
operation documents.

  * •

Avoid tedious code operation switching, and development efficiency is less
sensitive to the technical capability of the developer.

  * •

The entire model iteration process is recorded and trackable through the
platform. The iteration history can be useful for further investigation of
model related issues, such as analyzing the source of bias and fairness
problems. It can also be used to spot, share and promote best practices when
dealing similar tasks.

##  7 Appendix II: Screenshots of YMIR system UI

Figure 8: YMIR System - Project List View Figure 9: YMIR System - Start a
Labeling Task Figure 10: YMIR System - Start a Training Task Figure 11: YMIR
System - Start a Data Mining Task Figure 12: YMIR System - Model Verification


#  Egeon: Software-Defined Data Protection for Object Storage

Raul Saiz-Laudo, Marc Sánchez-Artigas  Computer Science and Maths, Universitat
Rovira i Virgili
Tarragona, Catalonia, Spain

###### Abstract

With the growth in popularity of cloud computing, object storage systems
(e.g., Amazon S$3$, OpenStack Swift, Ceph) have gained momentum for their
relatively low per-GB costs and high availability. However, as increasingly
more sensitive data is being accrued, the need to natively integrate privacy
controls into the storage is growing in relevance. Today, due to the poor
object storage interface, privacy controls are enforced by data curators with
full access to data in the clear. This motivates the need for a new approach
to data privacy that can provide strong assurance and control to data owners.
To fulfill this need, this paper presents Egeon, a novel software-defined data
protection framework for object storage. Egeon enables users to declaratively
set privacy policies on how their data can be shared. In the privacy policies,
the users can build complex data protection services through the composition
of data transformations, which are invoked inline by Egeon upon a read
request. As a result, data owners can trivially display multiple views from
the same data piece, and modify these views by only updating the policies. And
all without restructuring the internals of the underlying object storage
system. The Egeon prototype has been built atop OpenStack Swift. Evaluation
results shows promise in developing data protection services with little
overhead directly into the object store. Further, depending on the amount of
data filtered out in the transformed views, end-to-end latency can be low due
to the savings in network communication.

###### Index Terms:

object storage, software-defined, serverless, data privacy

##  I Introduction

With the rapid growth in popularity of Cloud services, object storage systems
(e.g., Amazon S$3$, IBM COS or OpenStack Swift [1]) have gained momentum.
These storage systems offer consolidated storage at scale, with high degrees
of availability and bandwidth at low cost. Proof of that is the recent trend
of serverless computing. Due to the high difficulty of function-to-function
communication111Some works have shown that cloud functions can communicate
directly using NAT (Network Address Translation) traversal techniques.
However, direct communication between functions is not supported by cloud
providers., many serverless systems use object storage for passing data
between functions [2, 3, 4, 5, 6], which has revived the interest in this type
of object storage.

Although very useful for cloud applications, object storage systems offer a
small number of options to keep sensitive data safe. Few (or no) efforts have
been realized on security issues such as data confidentiality, data integrity,
or access control, to mention a few. For instance, online storage services
such as Amazon S$3$, or IBM COS, only provide server-side encryption for
protecting objects at rest [7, 8]. Similar words can be said for the access
control of individual objects222In general terms, cloud object stores enforce
access at the container level rather than at the object level., which is
currently either realized via simple object ACLs (Access Control Lists) as in
S$3$ [7], or not possible at all as in OpenStack Swift [9].

This poor interface is insufficient for many applications. For instance, it
does not enable in-place queries on encrypted data, transparent and secure
data sharing, and access control based on the content of an object. But also,
it is very difficult to make it evolve to meet the changing needs of
applications and withstand the test of time. In practice, most of these object
storage systems leave no other choice to modifying the system internals to
incorporate new security mechanisms at the object level. This requires a deep
knowledge of the system, extreme care when modifying critical software that
took years of code-hardening to trust, and significant cost and time (see, for
instance, [10], where it is described the “daunting” task of deploying new
erasure coding solutions in object stores such as OpenStack Swift [1] and Ceph
[11]).

Rather than relying on object storage systems to change, we advocate in this
paper to “work around” the traditionally rigid object storage APIs by
embracing a _software-defined_ approach. Similarly to software-defined
networking (SDN), we argue that the separation of the “control logic” from the
“data protection logic” can give the needed flexibility and ease of use to
enable users, programmers and sysadmins to custom-fit access control and
object protection. To give an example, pretend that upon certain conditions,
parts of an encrypted object need to be re-encrypted to share it with the
mobile users of the application. Further, these conditions may depend on the
contents of the object itself (e.g., on sensitive data such as sexual
orientation), which must always remain confidential from the server. Simply
put, what we pursue is to offer users the ability to succinctly express this
behavior at the object storage level, and enforce it by calling the
corresponding re-encryption modules.

Nevertheless, a software-defined solution to enhance object storage data
protection requires solving several issues at two levels:

  * •

At the control plane, by enabling the composition of per-object protection
services. These compositions should be expressed concisely and in a manner
agnostic to the data protection code and the remaining storage stack.

  * •

At the data plane, by making it truly programmable. To put it baldly, the data
plane should not only allow to plug-in new protection logic in the critical
I/O path, but to run it safely. In addition, it should enable the re-usability
of the protection capabilities, so that users can compose new data protection
controls.

In this research work, we present Egeon, a novel software-defined data
protection framework for object storage. Egeon exports a scripting API to
define privacy policies for protecting objects. These policies enable data
owners to declaratively set complex data protection services through the
composition of user-defined transformations run in a serverless fashion. These
functions represent the elementary processing units in Egeon, and may be re-
used and linked together to implement complex privacy policies. The major
feature of these transformations is that they are executed “inline” by Egeon
upon a standard Get request. In this way, users can trivially display multiple
views from the same object, and modify these views by updating the policies.
If some functionality to implement a view is missing, Egeon provides a simple
API to deploy new transformations and customize the access to data objects.

In this sense, one of the primary contributions of Egeon is the ability to
provide privacy-compliant transformed views of the underlying data on the fly.
Perception of privacy can vary broadly across applications. As an example, a
dataset created by a hospital may include personally identifiable information
(PII) that is not needed when it is processed by a data analytics engine.
Nonetheless, if the same dataset is accessed by medical personnel, a richer
view of it should be given. Thus, a practical system needs to support a range
of privacy preferences.

By adopting a software-defined storage architecture, Egeon allows users to
express their privacy preferences as policies in the control plane and produce
views conforming to the policies by running transformations in the data plane.
In this work, we focus on (cryptographic) transformations that process data as
streams, that is, as data is being retrieved from object storage nodes.
Consequently, the first bytes of transformed views are received as soon as
possible, which permits Egeon to scale to arbitrary object sizes without
important penalty on end-to-end latency.

The Egeon prototype we present in this research has been implemented atop
OpenStack Swift [1]. We took Swift because it is open source and a production
quality system. Its sizable developer community ensures that our new
properties are built on code that is robust and that will be soon evaluated.
It must be noticed that the design concepts underpinning Egeon are generic and
could be easily ported to other storage substrates. For example, object
classes allow to extend Ceph by loading custom code into Object Storage
Daemons (OSDs), which can be run from within a librados application [12].
Thus, with some effort, it would be possible to leverage object classes to
implement transformed views of data.

Our performance evaluation of Egeon shows promise in developing data
protection services with low overhead directly into the object storage. For
instance, the overhead of a NOOP policy, where a storage function simpy echoes
the input data, is of around $9$ ms. Also, depending on the amount of
protected data filtered out in the transformed views, end-to-end latency can
be even lower with Egeon due to the savings in network communication (up to
$72.1$x for a $4$G mobile use case).

Figure 1: Egeon’s architecture.

##  II Design

Egeon is a software-defined data protection framework that augments object
storage with composable security services to enforce users’ privacy
preferences over protected data. These services are built up as pipelines of
serverless functions. Fig. 1 illustrates an overview of Egeon’s architecture.
Our objective is to enable authorized users or applications to access
protected data without violating the privacy policies of data owners. We have
designed Egeon to make it easy the leverage of state-of-the-art privacy
solutions (such as content-level access control, homomorphic encryption,
encrypted keyword search, …) while preserving the normal data flow in the
consuming applications. Concretely, we achieve this by introducing a logical
separation between the _privacy plane_ , where data owners set their privacy
preferences, and the _data plane_ , where the creation of privacy-compliant
transformed views happens. This separation allows for heterogeneous policies
atop the same data without having to modify the system internals to enforce
advanced policies at the object level.

Egeon’s architecture consists of the following components:

Privacy Plane. The privacy plane in Egeon corresponds to the control plane of
a software-defined architecture [13, 14], but specialized for data protection.
In practice, this means that Egeon provides its own script language to assist
data owner in composing data protection services from elementary serverless
functions in the _data plane_. The textual, JSON-based language supports
conditions and compositions to build up inline privacy transformers (e.g., see
Listing 1). Moreover, Egeon offers an API to allow data owners to manage the
life-cycle of their data protection policies. For performance reasons, once
uploaded, the policies are automatically compiled into Java bytecode and
stored in the _Metadata Service_. For fast access, this service has been built
on top of Redis [15], an in-memory, low-latency key value store.

Data Plane. In Egeon, the data plane has a critical role. The data plane is
responsible for generating the privacy-compliant data views. And hence, it
must be extensible to accommodate new functionality that enables privacy
transformations on data. Particularly, in this realization of Egeon, we have
focused on inline privacy transformations as data is retrieved from storage
nodes HDDs. As mandated by the policies in the privacy plane, privacy
transformations are constructed from pipelines of user-defined functions
executed as serverless functions by Egeon. Namely, a user integrating a new
transformation only needs to contribute the logic. Resource allocation and
execution of the chain of transformations is automatically handled by Egeon,
bringing a true serverless experience to users.

To minimize execution overhead, since many cryptographic operations are CPU-
intensive, Egeon abides by the principles of reactive programming and runs a
transformation only when is strictly needed, instead of continuously on the
data streams. More concretely, Egeon extends the observer pattern [16] and
execute a certain transformation in the pipeline when an event occurs [17].
Consequently, Egeon better utilizes the available resources in the storage
servers by balancing the load across the chain of transformations. To better
understand this, pretend that a user wants to compute the average salary of
employees in a department $\mathtt{X}$. Now suppose that all the employee
records have been saved in a single JSON document with all the salary values
homomorphically encrypted. Thanks to Egeon reactive core, the transformation
to average the salary will only be run when the event
“$\mathtt{employee\,of\,department\,X}$” comes through the data stream,
thereby saving CPU resources.

###  II-A Threat Model

Specifically, Egeon enforces user’s privacy preferences via function
composition. That is, users are ensured that their data is transformed as it
goes through a pipeline of transformation functions before it is released to
applications. In the meantime, the original data remains end-to-end encrypted.

We assume an _honest-but-curious_ [18] storage servers, i.e., the server
performs the computations correctly but will analyze all observed data to
learn as much information as possible. We also presume the existence of an
identity service (IDS) such as OpenStack Keystone for user authentication. We
leverage this service for authentication of the storage functions. An IDS is a
standard requirement in multi-user systems and can even be a trustworthy
external entity.

Consumers of shared data are semi-trusted, in that they do not collude with
the servers to leak the data or keys. This is a reasonable assumption for
groups of data consumers that are acquainted with each other. Further, Egeon
assumes that the applications behave correctly and do not hand out user keys
to malicious parties. Finally, we assume state-of-the-art security mechanisms
to be in place for user devices, and that all parties communicate over secure
channels.

In this setting, Egeon enforces _data confidentiality_ , making sure that the
adversary learns nothing about the data streams, except what can be learned
from the transformed views.

Robustness. While Egeon is able to handle various types of failures in
practice, provable robustness against misconfigured, or even malicious privacy
policies, and data producers is out of scope for this research. A malicious
user sending corrupted tokens cannot compromise privacy but could alter the
output of a transformed view.

###  II-B Privacy Plane

In the privacy plane, Egeon provides the capabilities for data owner to set
their privacy preferences —i.e., user-centric privacy—, and what
transformations will be required to apply to enforce a privacy policy. These
transformations are specified by their unique name, and their existence is
verified when the privacy policy is to be compiled. A privacy policy applies
to a single object. In this paper, we do not consider the question of how to
set privacy policies for group of objects and how they should look like. This
question has been left for future work.

In Egeon, targeted data objects in the privacy policies are specified by its
full resource path. Following OpenStack Swift specs [1], the access path to an
object is structured into three parts:
${\small\mathtt{/account/container/object}}$. As an example, for the
${\small\mathtt{rose.jpg}}$ object in the ${\small\mathtt{images}}$ container
in the $1234$ account, the resource path is:
${\small\mathtt{/1234/images/rose.jpg}}$.

Data owners can translate their preferences over an object to a set of
transformations by mapping them in a JSON-based schema language. In addition
to some meta-information (e.g., policy identifier), this schema permits data
owners to formalize conditions at the policy level using a rich set of
operators such as ${\small``\mathtt{StringLike}"}$,
$\small``\mathtt{NumericLessThan}"$, etc. Importantly, the language enables
data owners to build date expressions using operators like
$\small{``\mathtt{DateNotEquals}"}$, which makes it possible to express
temporal restrictions. For instance, pretend that a data owner wishes to
prevent that a document can be accessed on weekends. She could indicate this
through the date expression:
${\footnotesize\mathtt{``DateNotEquals":\left\\{``Day":[``Sat",``Sun"]\right\\}}}$.

More interestingly, this schema allows composing complex data protection
transformations from elementary UDFs. This can be achieved by adding each
individual UDF as a step in the transformation pipeline defined in the JSON
object ${\small``\mathtt{Action}"}$. This object contains two name-value
pairs: ${\small``\mathtt{StartAt}"}$, which indicates the first transformation
in the pipeline, and ${\small``\mathtt{Steps}"}$, which is another JSON object
that specifies the transformation UDFs along with their input parameters.
Since transformations run only when the corresponding events come through the
data stream, this schema allows data owners to specify the observed events for
each transformation to execute. To do so, there exists a field named
${\small``\mathtt{EventType}"}$ to signal the event to be observed by a
particular transformation UDF. A typical ${\small``\mathtt{EventType}"}$ block
looks like this:

⬇

{

"Type": "<type_of_event>",

"Input": [<parameter_block>, ...],

}

where the ${\small``\mathtt{Type}"}$ field specifies the type of an event
(e.g., an XPath [19] event) and the array ${\small``\mathtt{Input}"}$ lists
the parameters that are required for this type of event. For instance, if a
data owner wanted to apply a transformation UDF over all
$\small\mathtt{salary}$ elements of an XML document, she could do so by
setting an XPath event as follows:

⬇

{

"Type": "XPathEvent",

"Input": [{"Predicate": "//salary"}],

}

Similarly, a transformation UDF block is defined as follows:

⬇

{

"Id": "<identifier_of_UDF>",

"EventType": "<event_block>",

"Input": [<parameter_block>, ...],

"Next": (<identifier_of_UDF>|"End")

}

The ${\small``\mathtt{Id}"}$ field is a string which uniquely identifies the
UDF, while the ${\small``\mathtt{Input}"}$ field permits to specify the
parameters for the transformation UDF (e.g., the targeted security level of a
cryptosystem). Finally, the ${\small``\mathtt{Next}"}$ field indicates the
next step to follow in the pipeline, or ${\small``\mathtt{End}"}$ to indicate
the end of the chain of transformations.

An example of a real policy can be found in Listing 1. This policy provides
transformed views over a JSON file containing employee records of the format:

⬇

{

"employee": {

"name": "Alice",

"identification": {

"SSN": "32456677"

},

"salary": 50000

}

...

}

As a first transformation in the chain, this policy uses content-level access
control [9] (CLAC). Very succinctly, CLAC works as follows. It assigns
targeted JSON elements an object label (${\small\mathtt{olabel}}$) and each
user a user-label ($\mathtt{ulabel}$). Then, it allows to define rules in the
form of $(\mathtt{ulabel},\mathtt{olabel})$, which means that the JSON
elements labeled with any of the $\mathtt{olabel}$s are allowed to be read by
the users labeled with the corresponding $\mathtt{ulabel}$s. To indicate what
JSON items to protect, CLAC uses JSONPath in this case.

In this policy, we assume two types of users: treasurers with user label
$``\mathtt{treasurer}"$ and regular users with label
${\small``\mathtt{user}"}$. We protect the salaries with the object label
$``\mathtt{sensitive}"$ and specify the single rule
$(``\mathtt{treasurer}",``\mathtt{sensitive}")$, which means that only
treasurers will have access to the salaries. The field $``\mathtt{salary}"$ is
identified using the JSONPath expression: $`\mathtt{\$.employee.salary}$’
(Listing 1, line $14$).

The second transformation applies homomorphic encryption on the field
$``\mathtt{salary}"$ to prevent the servers from learning the employee
salaries [20], while computing the average salary of employees (Listing 1,
lines $20$-$30$).

As a final transformation in the chain, the policy uses proxy re-encryption
[20] to convert the homomorphically encrypted average salary to a ciphertext
under the receiver’s key. Thus, the transformed view can be decrypted by the
receiver, without the data owner having to share her private key nor
performing any encryption for the receiver on her personal device.

To wrap up, this policy will generate two transformed views of the same data.
For regular users, it will only be executed the first step (lines $10$-$19$):
the CLAC transformation. Due to lack of permissions, the CLAC module will
eliminate the encrypted $``\mathtt{salary}"$ field, and output a transformed
view with the rest of information. For a treasurer, it will output the same
view as any regular user (without individual salaries), but enriched with the
average salary encrypted under her public key thanks to proxy re-encryption
(Listing 1, lines $31$-$37$).

We want to note that the different transformations UDF only execute when the
corresponding JSONPath events come along. To wit, proxy re-encryption will
only be run one time, after the JSON field named
$``\mathtt{average\\_salary}"$ is added at the end of the response by the
second transformation in the chain.

⬇

1{

2 "Id": "employee.policy",

3 "Object": "v1/{account}/{container}/employees.json",

4 "Condition": {

5 "DateNotEquals": { "Day": ["Sat","Sun"] }

6 },

7 "Action": {

8 "StartAt": "Step1",

9 "Steps": {

10 "Step1": {

11 "Id": "CLAC",

12 "EventType": {

13 "Type": "JSONPathMarkerEvent",

14 "Input": [{"Predicate":"$.employee.salary", "olabel": "sensitive" }]

15 },

16 "Input": [{"ulabel": "treasurer",

17 "olabel": "sensitive" }],

18 "Next": "Step2"

19 },

20 "Step2": {

21 "Id": "SUM",

22 "EventType": {

23 "Type": "JSONPathEvent",

24 "Input": [{"Predicate":"$.employee.salary"}]

25 },

26 "Input": [{"average": true},

27 {"keyOwner": "meta://Alice/keys/hom",

28 {"output":"$.average_salary"}],

29 "Next": "Step3"

30 },

31 "Step3": {

32 "Id": "PRE",

33 "EventType": {

34 "Type": "JSONPathEvent",

35 "Input": [{"Predicate":"$.average_salary"}]

36 },

37 "Next": "End"

38}}}

Listing 1: A sample policy to process employee records.

As a final word, this example clearly displays how Egeon is capable of
performing real-time privacy transformations atop the same data object for a
variety of application scenarios, thus enhancing the rigid interface of object
storage systems.

###  II-C Data Plane

The focus of Egeon is on inline privacy transformations, where data streams
are “observables” and user-defined privacy transformations are “observers”
subscribed to the data streams. As as soon as an event is observed, it will be
delivered to the subscribed observers. If there are no events on the data
stream then the original data stream is pushed back to the user. In this
sense, a privacy transformation is nothing but a function taking an observable
as input and returning another observable as its output. This design has the
advantage that transformations can be chained together to generate complex
data views compliant with the policies in the privacy plane.

Runtime. Currently, Egeon’s runtime is Java-based. Thus, the chain of
transformations is run within a Java Virtual Machine (JVM) wrapped within a
Docker container to guarantee a high level of isolation between two different
data transformations.

Policy Enforcement. Upon a new Get request, Egeon starts up a thread inside
the JVM to perform three tasks. We refer to this thread as the “master
thread”. The three tasks in order of execution are:

  1. 1.

_Policy loading_ , where the master thread loads the policy into memory and
evaluates its conditions clauses.

  2. 2.

_Observable setting_ , where the master thread opens a data stream to the
target object, namely, the observable, if the policy conditions are fulfilled.
To this aim, it creates an instance of the appropriate subclass of the
abstract class $\mathtt{StreamBuilder}$ that the Egeon’s engine leverages to
start parsing the object. Subclasses are required since the specific logic to
parse the data stream and generate the events depends on the type of file.
Specifically, Egeon picks up the proper $\mathtt{StreamBuilder}$ subclass
based on the object extension (e.g., $``\mathtt{.json}"$ for JSON documents)
using _factory_ methods.

  3. 3.

_Transformations setting_ , where the master thread makes an instance of each
transformation UDF in the pipeline and chains them together. The
$\mathtt{StreamBuilder}$ subclass generates events as the data is being
parsed, and notifies the subscribed transformation UDFs in the same order as
dictated in the privacy policy. To wit, in Listing 1, upon the JSONPath event
$`\mathtt{\$.employee.salary}$’, Egeon will execute first the CLAC
transformation, followed by the SUM transformation.

In Egeon, we assume that an observable can only handle one event at a time. We
adopted this design to minimize compute resources at the storage layer, so
that both the data stream and all its transformations operate in the same
thread, in our case, the master thread. Nevertheless, this can be easily
changed by switching to a different thread and integrating some additional
logic for coordinating the threads.

Since each transformation UDF acts as an observer, another responsibility of
the master thread is to subscribe each privacy transformation to the events
specified in the policy. To this aim, it invokes the method
${\tiny\mathtt{install(Event\,event,UDF\,observer)}}$ in the
${\small\mathtt{StreamBuilder}}$ class, where the parameter
${\small\mathtt{observer}}$ is the transformation UDF bound to the
${\small\mathtt{event}}$.

Extensibility. At the time of this writing, Egeon implements three types of
data sources: XML, JSON and CSV documents, a number of events including XPath
and JsonPath expressions, CSV field and records, etc., and multiple
transformation UDFs (see §II-D for further details). However, Egeon is
extensible, and new events, observables and observers can be incorporated by
extending the abstract classes ${\small\mathtt{Event}}$,
${\small\mathtt{StreamBuilder}}$ and ${\small\mathtt{UDF}}$, respectively.

Due to space constraints, we only show here an example of a transformation
${\small\mathtt{UDF}}$ to perform summations on ciphertexts [20] to see how
easy it is to code a transformation UDF (Listing 2).

⬇

1package com.urv.egeon.function;

2

3import com.urv.egeon.runtime.api.crypto.Homomorphic;

4import com.urv.egeon.runtime.api.parser.UDF.ContextUDF;

5import com.urv.egeon.runtime.api.parser.UDF.UDF;

6import com.urv.egeon.runtime.api.parser.event.Event;

7

8public class Sum extends UDF {

9 private Homomorphic accum = new Homomorphic();

10

11 @Override

12 public Event update(Event e, ContextUDF ctx) {

13 try {

14 this.accum.add((String) e.getValue());

15 } catch (Exception ex) {

16 // first execution of the UDF

17 this.accum.setKeys((String) ctx.getParameter("keyOwner"));

18 this.accum.setCipher(this.accum.fromSerial((String) e.getValue()));

19 } finally {

20 return e;

21 }

22 }

23 @Override

24 public Object complete(ContextUDF ctx) { ... }

25}

Listing 2: A transformation UDF to perform summations on ciphertexts.

As shown in Listing 2, a UDF has two methods: the method $\mathtt{update}$,
which is invoked every time a new subscribed event is emitted, and the method
$\mathtt{complete}$, which is called when the data stream is finalized
(empty). The $\mathtt{update}$ method has two arguments of type
$\mathtt{Event}$ and $\mathtt{ContextUDF}$. The first argument encapsulates
the details of the emitted event. For instance, for the homomorphic summation
UDF of Listing 2, this may mean a JSONPath event, alongside the value of the
selected field by the JSONPath expression (e.g., an encrypted salary value),
and accessible via the method $\mathtt{getValue}$ (Listing 2, line $14$). The
$\mathtt{ContextUDF}$ encapsulates the access to the request metadata, such as
HTTP headers and cryptographic keys and tokens sent out by the client, the
object’s metadata, and specific parameters required for the UDF to work, such
as the data owner’s public key to operate on the encrypted values (Listing 2,
line $17$). All this information is automatically made available by Egeon to
the transformation UDF. This includes the input parameters set in the privacy
policy (e.g., Listing 1, lines $26$-$28$).

It is worth to mention here that the input arguments whose values have the
format of $``\mathtt{meta://key}"$ are automatically downloaded from the
Metadata Service using the key $``\mathtt{key}"$. In this way, a data owner
can change the input parameters (e.g., her homomorphic public key) without
having to re-compile the policy. An example of this can be found in Listing 1,
line $27$, for the argument $``\mathtt{keyOwner}"$, whose value is retrieved
from the Metadata Service behind the scenes, and made accessible to the
summation UDF via the context (Listing 2, line $17$).

The purpose of the method $\mathtt{complete}$ is to provide a hook for
developers to perform final computations and append their result at the end of
the data stream. For instance, this could be useful to compute the average
over encrypted data and append the result as new item at the end of a JSON
document.

###  II-D Data Transformation UDFs

Egeon comes up with a library of reusable functions (UDFs) for inline data
protection. While some of these functions apply cryptographic transformations,
others act on raw data, e.g., by filtering out protected parts of a JSON
object to non-privileged users [9]. All functions are composable to provide
complex transformed data views. These are the following:

Homomorphic encryption (HOM). HOM is a cryptosystem (typically, IND-CPA
secure) that allows the server to perform computations directly on encrypted
data, the final result being decrypted by the user devices. For general
operations, HOM is prohibitively slow. However, it is efficient for summation.
To support summation, along with proxy re-encryption (PRE), we adopted the
homomorphic cryptosystem of [20]. We chose this scheme, because it allows
secure data sharing and is tailored to mobile platforms and constrained IoT
devices. Concretely, we implemented two UDFs:

  * •

Summation (SUM): This UDF supports the summation of ciphertexts, such that the
result is equal to the addition of the plaintext
values:$\,\mathtt{Enc}(m_{1})\cdot\mathtt{Enc}(m_{2})=\mathtt{Enc}(m_{1}+m_{2})$.

  * •

Re-Encryption (PRE). Succinctly, PRE allows the storage servers to convert
ciphertexts under the data owner’s key to ciphertexts under authorized users
keys without leaking the plaintext. Therefore, the data owner can securely
share data with other users, i.e., without sharing her private key nor
performing any encryption for them on her personal device. To do so, the data
owner $d$ solely needs to issue a re-encryption token for a user $u$ based on
his public key $pk_{u}$ as the $\mathtt{Token}_{d\rightarrow u}$. With this
token, the PRE UDF can automatically re-encrypt data on behalf of the data
owner without her intervention. Further, the re-encryption tokens are
unidirectional and non-transitive.

For both UDFs, we assume integers of $\leq 32$ bits with $128$-bits of
security. The implementation makes use of the optimal Ate pairing [21] over
Barreto-Naehrigopera elliptic curve [22], and also applies the Chine Remainder
Theorem (CRT) to optimize decryption [20]. For all this cryptographic
processing, we use the RELIC toolkit [23].

Keyword search (SEARCH). To allow keyword searches (as the SQL“ILIKE”
keyword), we make use of a cryptographic scheme for keyword searches on
encrypted text [24]. As above, we have chosen this scheme because it is multi-
user. To put it baldly, before storing an object, the data owner first selects
the users with whom she wants to share her data and then encrypts it with
their public keys. To search for keywords in the shared object, a user makes a
trapdoor $\mathtt{Trap}_{W}$ for the keyword set $W$ using his private key,
and then sends it to the server. The server runs the SEARCH UDF, which takes
the public key of the user, the trapdoor $\mathtt{Trap}_{W}$ and the encrypted
text, and returns “yes” if contains $W$ or “no” otherwise. As expected, this
scheme is proved secure against chosen keyword attacks (IND-CKA).

One major advantage of this scheme is its short ciphertext size. Concretely,
for $n$ users, it requires $(n+\ell+1)\cdot L1$ bits, where $\ell$ is the
number of keywords and $L1$ is the bit length of the underlying finite field
$\mathbb{F}_{q}$, which is much smaller than the deployment of $n$ separate
instances of a public key searchable encryption scheme, one for each user. For
the implementation of this scheme, we use the “SS$512$” elliptic curve, a
symmetric curve with a $512$-bit base field, which provides a security level
of $80$-bits, from the jPBC library [25].

Content-level access control (CLAC). As an example of a non-cryptographic
function, we decided to implement content-level access control [9]. The
central idea of CLAC is to enforce access control at the content level to
restrict who reads which part of a document. To give a concrete example,
consider that a hospital stores its patient records as big JSON object. These
records should be accessed differently by different personnel. For example, a
“doctor” could see health information from her patients, while a
“receptionist” should only view basic profile information about the patients.
With CLAC, a data owner can define content-level policies to censor access to
parts of a data object. Remember that in object storage systems such as Swift
or Amazon S$3$, once an object is made accessible to someone, she retrieves
the full content of the object. So, there is no way to hide out sensitive
information to that user.

Our implementation of CLAC overcomes this limitation. As introduced in §II-B,
CLAC borrows the LaBAC model (Label Based Access Control Model) [9]. Either be
an XML element, a JSON element, or a CSV column, an object label
(${\small\mathtt{olabel}}$) is assigned on the targeted item. Similarly, each
authorized user is given a user label ($\mathtt{ulabel}$). Then, the LaBAC
model works by specifying tuples of rules in the form of
$(\mathtt{ulabel},\mathtt{olabel})$, which tell that only the users labeled
with $\mathtt{ulabel}$ can access the items labeled with that
$\mathtt{olabel}$. For instance, if only users with the user label
$``\mathtt{manager}"$ were authorized to access items labeled with
$``\mathtt{restricted}"$, a data owner should have to set the rule
$(``\mathtt{manager}",``\mathtt{restricted}")$ to effectively formalize access
control. As in the LaBAC model, our implementation admits hierarchies of both
$\mathtt{ulabel}$s and $\mathtt{olabel}$s to rank users and objects.

One interesting side effect of our reactive data plane is that our CLAC
implementation is generic, and not tied to a specific file type. What changes
is the mechanism to identify the items, which depends on the object type. That
is, for XML, an XPath expression should be used to indicate that a certain
element has $``\mathtt{restricted}"$ access, while for a JSON document, a JSON
predicate should be used in its stead. We have abstracted this coupling by the
definition of specific marker events as shown in Listing 1, lines $22$-$25$.

##  III Implementation

We have constructed Egeon by extending Zion [26], a data-driven serverless
computing middleware for object storage. In particular, we have implemented
Egeon on top of OpenStack Swift [1], a highly-scalable object store.

OpenStack Swift is split into several components. The main components are the
object and proxy servers. While the object servers are responsible for the
storage and management of the objects, the proxy servers expose the RESTful
Swift API (e.g., $\mathtt{GET\,/v1/account/container/object}$ to get object
content) and stream objects to and from the clients upon request.

To be as non-intrusive as possible, the only modification we perform in the
default Swift architecture is the deployment of a custom Swift middleware to
intercept $\mathtt{GET}$, or read, requests at the proxy servers [27]. This
middleware also provides a simple API to manage the life-cycle of privacy
policies. Essentially, it communicates with the Metadata Service to store and
retrieve the privacy policies for protected data objects. Recall that the
Metadata Service leverages Redis [15] to yield sub-millisecond access latency
to metadata. To optimize request matching even further, we have collocated the
Redis instance with the proxy server.

As Zion, Egeon uses containers to sandbox the execution of the chain of
privacy transformations. However, contrary to Zion, which is a general-purpose
serverless platform, Egeon employs a single, optimized serverless function to
produce the privacy-compliant views of the underlying data. This function
deserializes the compiled privacy policy, loads it into memory, evaluates the
conditions from the clauses, and if it “applies”, it runs the the pipeline of
UDF transformations. This design has two main benefits. On the one hand, Egeon
runtime starts up faster. On the other hand, UDF transformations enjoy of a
great level of isolation. Simply put, they have neither direct network access
nor access to the local Linux file system, among other namespaced resources,
which protects the whole system from malicious transformations.

Also, to enhance response time for policies that are accessed frequently,
Egeon runtime deploys a cache for policies using the Google Guava caching
library [28] configured with a least-recently-used (LRU) eviction policy.

Resource allocation is managed by Zion. Egeon does not contribute any
optimization at this level. When a read request comes along, our Swift
middleware contacts the Zion service, which manages the containers in the
object servers, and starts up a new one if necessary.

##  IV Evaluation

In this section, we evaluate key aspects of Egeon’s design and our prototype
implementation. First, we begin with a series of microbenchmarks to judge
aspects such as system overhead, throughput and the performance of the
cryptographic operators in isolation. Finally, we assess Egeon’s flexibility
to compose complex data views.

System setup. All the experiments have been conducted in a cluster of $8$
machines: $2$ Dell PowerEdge R320 machines with $12$GB RAM, which operate as
Swift Proxy servers, and $6$ Dell PowerEdge R320 machines with $8$GB RAM and
$4$-core CPUs, which act as object servers. The version of OpenStack Swift is
Stein $5.2.0$. All the machines run Ubuntu Server $20.04$LTS and are
interconnected through $1$GbE links. The client machine for the experiments is
equipped with a Intel Core i5-4440 CPU with 4 cores and $8$GB RAM.

Competing systems. In some tests, we have compared Egeon against plain Zion
[26] and Vertigo [29], all deployed in the same Swift cluster as above.
Concretely, we have used Zion as a baseline to assess the overhead added by
Egeon’s software-defined architecture to the original Zion design, while we
have chosen Vertigo as an example of a general-purpose, software-defined
object storage system. As Egeon, Vertigo allows users to create pipelines of
storage functions, each implemented as an OpenStack Storlet [30]. Hence, it is
a good representative to act as a proving ground for the performance of Egeon
against a similar software-defined architecture. It must be noticed that the
control plane in Vertigo is programmatic, while in Egeon is declarative
through the use of JSON-based privacy policies.

###  IV-A Microbenchmarks

We have run several microbenchmarks:

Cryptographic operations. To better understand the sources of overhead
incurred by Egeon, we examined the throughput of the individual transformation
UDFs, since different privacy policies may result in various transformation
mixes. For each type of cryptographic transformation, we measured the number
of operations per second that the Egeon runtime can perform on a object server
in the data plane, as well as the latency. The meaning of each operation
depends on the specific type of the cryptographic transformation UDF. For HOM,
this refers to the summation of two encrypted $32$-bit integers. For PRE, it
refers to the proxy re-encryption of a single encrypted $32$-bit integer,
while for SEARCH, it represents the search of a keyword in an encrypted
document with the same keyword. The results of this experiment are given in
Table I. As expected, we can observe that the latency of the cryptographic
operations is in the order of a few milliseconds, which is acceptable for many
use cases. Due to the added latency of the cryptographic transformations, a
reactive data plane such as that available in Egeon, which is driven
exclusively by the events appearing in the data streams, can be of great help
to define privacy policies that minimize the number of cryptographic
operations (for instance, by skipping unneeded data in the first steps of the
transformation chain).

Overhead. To provide a full picture of the overheads incurred by Egeon, we
measured the latency introduced by Egeon to the I/O path with respect to Zion
and vanilla Swift. To measure the overhead, we utilized the Time to First Byte
(TTFB), which captures how long the client needed to wait before receiving its
first byte of the response payload from the Swift servers. To make
measurements more precise, we colocated the client with one of the Swift proxy
servers. As a client, we used pycurl to generate the Get requests for three
different data file sizes. For each object size, we performed $1$K requests.
For Zion, each request caused the invocation of a NOOP function that simply
echoes the input stream to the output (see Listing 1 in [26] for further
details). For Egeon, we set up a NOOP policy which includes a single NOOP UDF
in the transformation chain. This UDF does nothing:

⬇

1package com.urv.egeon.function;

2

3import com.urv.egeon.runtime.api.parser.UDF.ContextUDF;

4import com.urv.egeon.runtime.api.parser.UDF.UDF;

5import com.urv.egeon.runtime.api.parser.event.Event;

6

7public class Noop extends UDF {

8 @Override

9 public Event update(Event e, ContextUDF ctx) { return e; }

10 @Override

11 public Object destroy(ContextUDF ctx) { return null; }

12}

Listing 3: A no-operation (NOOP) UDF.

The results are given in Fig. 2. As seen in this figure, Zion and Egeon are on
par, which demonstrates that Egeon software-defined architecture adds little
overhead to Zion. With respect to vanilla Swift, both systems add around $9$ms
of extra latency, which can be considered very small. To wit, serverless
function invocation in major cloud providers usually take between $25$ to
$320$ms in warm state [31].

Since Zion does not support the pipelining of functions, we compared Egeon
against Vertigo. Recall that Vertigo enables users to chain several Storlets
together, where each Storlet can implement some reusable storage function such
as decryption, compression, etc. We repeated the same experiment as above, but
evaluating chains of increasing length. For Egeon, we set up chains of NOOP
UDFs, while for Vertigo, we did the same, but for pipelines of NOOP Storlets.
The results are depicted in Fig. 3. We can see that while the overhead keeps
constant in Egeon, Vertigo shows a linear increase in latency. The reason for
such a difference is the reactive core of Egeon, which does nothing if the
transformations are not subscribed to any event. Vertigo, however, wires each
Storlet with their neighbors in the chain, which takes some time, albeit each
of them just copies the input to the output. This strongly reinforces the idea
that for a software-defined data protection system to be useful, it is not a
good idea to route the data streams through a pipeline of functions, but
rather to act on them when it is strictly needed. Indeed, Vertigo’s overhead
is more than one magnitude higher than Egeon’s overhead as shown in Fig. 3.

TABLE I: Performance of cryptographic primitives available in Egeon. Transformation UDF |  Throughput (ops/sec) |  Latency (ms)
---|---|---
Homomorphic Addition (SUM) | $616$ | $1.62$
Proxy Re-Encryption (PRE) | 137 | $7.29$
Keyword Search (SEARCH) | 166 | $6.02$

(a)  (b)  (c)

Figure 2: Time to First Byte (TTFB) for different object sizes.

(a)

(b)

Figure 3: Overhead of chain setup of Egeon versus Vertigo.

Throughput. As a final microbenchmark, we quantified the impact of Egeon on
the system throughput. As above, Egeon was compared to Zion and vanilla Swift
to give real sense of its performance. For this experiment, we utilized the
getput benchmarking tool suite [32] for Swift. And in particular, the gpsuite
to conduct parallel tests with multiple clients. More concretely, we run
gpsuite in one of the Swift proxy servers for $10$ seconds and for different
object sizes. We considered a replication factor of $3$, and instrumented
gpsuite to stress $3$ out of the $6$ object servers in the data plane. As in
the overhead test, a NOOP function call per request was made for Zion and a
NOOP policy plus NOOP UDF for Egeon. Table II reports the maximum throughput
in operations per second attained by each system. Similarly to what was
observed for the overhead, Egeon and Zion perform in similar terms. More
interestingly, as the object size increases, the gap between both Egeon and
Zion and Swift grows. We investigated this issue and we found that this
happens due to a higher CPU interference caused by the JVM used to run the
Egeon logic and the NOOP code in Zion, respectively.

(a)

(b)

Figure 4: Throughput and latency of Egeon under a multi-client setting.

Also, Fig. 4a plots the throughput for an increasing number of emulated
clients for a $1$MB object, which exhibits the same behavior as before. That
is, Egeon and Zion showing a similar performance, while Swift delivering a
much higher throughput due to the absence of any computation in the I/O path.
Finally, Fig. 4b illustrates Egeon’s slowdown relative to vanilla Swift,
calculated as
$\mathrm{Slowdown=\frac{\textsc{Egeon}\,download\,time}{Swift\,download\,time}}$,
as a function of the object size ($x$-axis) and the number of concurrent
clients ($y$-axis). As can be seen in the figure, the slowdown factor does not
increase steeply. Rather, it increases gradually in both axes, never doubling
the latency. This indicates that pushing down data protection logic to the
storage may be acceptable for many applications.

TABLE II: Maximum throughput (ops/sec) for different object sizes. System | Object size
---|---
|  $100$KB |  $1$MB |  $10$MB
Swift | 157,81 | 111,43 | 31,62
Zion | 140,72 | 79,69 | 21,17
Egeon | 140,56 | 79,59 | 21,26

###  IV-B Applications

To evaluate the composability of Egeon, we have designed two privacy policies
that capture the different complexities of real-world applications. These
applications are the following:

Covid-$19$ use case. In this use case, we demonstrate the same policy of
Listing 1, but applied to healthcare. We use the JSON file reported by the US
government that summarizes the patient impact on healthcare facilities caused
by Covid-$19$ [33] (April 2021). Specifically, we exchange the user label
$\mathtt{``treasurer"}$ by $\mathtt{``state\,coordinator"}$, and label the
field that reports the sum of patients hospitalized in a pediatric inpatient
bed in $7$-day periods [FAQ-$10$.b)] as $\mathtt{``sensitive"}$, as it reveals
which hospitals may be collapsed. The rest of information is ignored. As a
result, the transformed view for state officials only bears a single
homomorphically encrypted value that aggregates the sum of all healthcare
facilities. As in Listing 1, the policy links $3$ UDFs:
CLAC$\rightarrow$HOM$\rightarrow$PRE. To play out with the file size, we split
this dataset into three smaller files based on increasingly smaller time
periods: year, month and week.

Adult dataset [34] use case. This dataset in CSV format from the UCI Machine
Learning Repository [34] has $48842$ records and $14$ attributes. Some of
these attributes can leak sensitive information such as race and occupation.
For this use case, we have decided to protect the attribute $\\#7$:
occupation, with the SEARCH scheme to allow for type-of-employment searches on
encrypted text. To prove composability, we have used CLAC to protect three
attributes out of the four attributes chosen for this experiment. We have used
one object label: $\mathtt{``sensitive}"$, and one user label:
$\mathtt{``HR\,manager"}$, so that only a human resources manager can retrieve
the three protected columns. Further, we have encrypted other fields to
increase the file size to $134$MB, to later split it into $3$ smaller files
based on the attribute $\\#6$: marital-status. The policy is as follows (some
fields have been omitted for brevity):

⬇

{

"Object": "v1/{account}/{container}/adult.csv",

"Action": {

"StartAt": "Step1",

"Steps": {

"Step1": {

"Id": "CLAC",

"EventType": {

"Type": "ColumnMarkerEvent",

"Input": [{"columns": [2,6,7], "olabel": "sensitive" }]

},

"Input": [{"ulabel": "HR manager", "olabel": "sensitive" }],

"Next": "Step2"

},

"Step2": {

"Id": "SEARCH",

"EventType": {"Type": "ColumnEvent", "Input": [{"column":7}]},

"Next": "End"

}}}

TABLE III: Network Speeds.  Network | 4G | Fiber | LAN
---|---|---|---
Median speed (Mbps) |  $28.9$ [35] |  $55.98$ [36] |  $887$ (SpeedTest)

Experiment. In this test, we measure the time to download the raw files
directly from Swift against the time to download the transformed views
generated by Egeon. The goal is to decide if it is worth to push the privacy
transformations into the object store instead of running them on the user
devices and VMs, so that software-defined data protection is within reach. To
do so, we have capped the ingoing bandwidth of our client machine to emulate
different network speeds and customary scenarios: Fiber network speeds to
emulate home and business users, $4$G network bandwidth to emulate mobile
users, and finally, LAN to simulate a scenario where the client and Swift
servers reside on the same local area network (e.g., a university intranet).
The exact network speeds are listed in Table III. We performed $1$K executions
per object size and network speed.

(a)

(b)

Figure 5: Performance of Egeon in two composite policies.

The results are plotted in Fig. 5a for the Covid-$19$ use case, and in Fig. 5b
for the Adult dataset. Error bars display the standard deviations of results,
which are indeed very narrow. Non-surprisingly, we can see that Egeon lowers
the download time significantly for the slow $4$G and fiber connections, which
means that pushing down privacy transformations to storage is a good deal
better than the naive approach of encrypting data on the client side and
retrieve the whole file as alleged by cloud providers such as AWS for S$3$.
The savings in some scenarios can be dramatic such as in the Covid-$19$ use
case, where just a few bytes (e.g., aggregates such as SUM, COUNT and AVG,
etc.) are consumed by the application, reaching $72.1$X speedup for $4$G
mobile terminals. For the LAN setting, the benefits are not so clear, and for
the Adult dataset, Egeon shows a slowdown factor of $3.3$X in the worst case
due to the heavy computations associated with keyword search—actually, the
test primitive of SEARCH requires three pairing operations [24]. Either way,
we believe that Egeon’s fine-grained data protection capabilities outweigh the
slight loss of performance.

##  V Related Work

Software-defined storage systems. A first category of related work comprises
software-defined approaches for storage, and in particular, for object storage
systems. The common feature of these approaches is that they break the
vertical alignment of conventional storage infrastructures by reorganizing the
I/O stack to decouple the control and data flows into two planes of
functionality—control and data. A number of proposals have followed this
approach, including IOFlow [37], sRoutes [38], Retro [39], Vertigo [29] and
Crystal [13, 14].

Among them, only Vertigo and Crystal have been tailored to object storage. As
Egeon, both systems have been deployed atop OpenStack Swift. But unlike Egeon,
their data plane is based on OpenStack Storlets [30]. A Storlet is a piece of
Java logic that is injected into the data plane to run custom storage services
over incoming I/O requests. As in Egeon, this design increases the modularity
and programmability of the data plane stages, fostering reutilization.
However, Storlet-made pipelines are not reactive, wasting resources when we
are only interested in specific elements of the data stream. Moreover, the
Storlet-enabled data plane of Vertigo and Crystal emphasizes control-flow over
data-flow, making it hard to explicitly represent the (cryptograhic)
transformations of objects. Per contra, Egeon’s data plane is driven solely by
the events showing up in the data streams, which makes it easy to reuse the
same transformations over and over again on different data. Only the events
must be re-defined in the policies.

Finally, it is worth to note that to the best of our knowledge, we are not
aware of another software-defined storage system that automatically enforces
privacy policies along the I/O path as Egeon. Software-defined security has
remained within the boundaries of software-defined networking (see, for
instance, Fresco [40]). The only exception is the recent vision paper [41] on
software-defined data protection. Like Egeon, [41] argues that the key ideas
of software-defined storage can be translated to the data protection domain.
However, the approach of [41] is radically different. Instead of adding
privacy controls to the I/O stack of a disk-based object storage system, [41]
assumes all in-storage processing to occur on FPGAs and “smart storage”
devices, for we see [41] as an orthogonal work to us.

Privacy Policy Enforcement. There exist many systems that enforce privacy
policies automatically. Most of these systems resort to Information Flow
Control (IFC) as a means to control how information flows through the system.
See, for instance, Riverbed [42], which uses IFC to enforce user policies on
how a web service should release sensitive user data. In contrast to these
systems, Egeon follows a software-defined approach to leverage the storage
resources and enforce the privacy policies where data is. Similar to our
transformation chains, Zeph [43] proposes to enforce privacy controls
cryptographically but over encrypted stream processing pipelines. Specifically
for storage, Guardat [44], at the block level, and Pesos [45], at the object
level, enable users to specify security policies, for instance, to stipulate
that accesses to a file require a record be added to an append-only log file.
Nonetheless, these systems do not permit the composition of advanced privacy
controls as Egeon, and thus, fall short to empower users with strong data
controllers.

##  VI Conclusions

As increasingly much more sensitive data is being collected to gain valuable
insights, the need to natively integrate privacy controls into the storage
systems is growing in importance. In particular, the poor interface of object
storage systems, which lacks of sophisticated data protection mechanisms,
along with the inherent difficulties to refactor them, have motivated us to
design and implement Egeon. To put in a nutshell, Egeon is a novel software-
defined data protection framework for object storage. It allows data owners to
define privacy policies on how their data can be shared, which permit the
composition of data transformations to build sophisticated data protection
controls. In this way, data owners can specify multiple views from the same
data piece, and modify these views by only updating the policies (e.g., by
modifying the chain of transformations that produce a particular view),
leaving the system internals intact. The Egeon prototype has been coded atop
OpenStack Swift. And our evaluation results demonstrate that Egeon adds little
overhead to the system, yet empowering users with the needed controls to
ensure strong data protection.

## Acknowledgment

This research has been partly supported by EU under grant agreement No. 825184
and the Spanish Government through project PID2019-106774RB-C22. Marc Sanchez-
Artigas is a Serra-Húnter Fellow.

## References

  * [1] OpenStack, “Swift,” https://docs.openstack.org/swift/, 2021.
  * [2] J. Sampé, G. Vernik, M. Sánchez-Artigas, and P. García-López, “Serverless data analytics in the ibm cloud,” in _19th ACM/IFIP Middleware Conference Industry (Middleware’18)_ , 2018, pp. 1–7.
  * [3] Q. Pu, S. Venkataraman, and I. Stoica, “Shuffling, fast and slow: scalable analytics on serverless infrastructure,” in _16th USENIX Symposium on Networked Systems Design and Implementation (NSDI’19)_ , 2019, pp. 193–206.
  * [4] I. Müller, R. Marroquín, and G. Alonso, “Lambada: Interactive data analytics on cold data using serverless cloud infrastructure,” in _2020 ACM SIGMOD International Conference on Management of Data (SIGMOD’20)_ , 2020, pp. 115–130.
  * [5] M. Sánchez-Artigas, G. T. Eizaguirre, G. Vernik, L. Stuart, and P. García-López, “Primula: A practical shuffle/sort operator for serverless computing,” in _21st International Middleware Conference Industrial Track (Middleware’20)_ , 2020, pp. 31–37.
  * [6] A. Mahgoub, K. Shankar, S. Mitra, A. Klimovic, S. Chaterji, and S. Bagchi, “SONIC: Application-aware data passing for chained serverless applications,” in _2021 USENIX Annual Technical Conference (USENIX ATC 21)_ , 2021, pp. 285–301.
  * [7] Amazon, “Amazon S3 Developer Guide,” http://aws.amazon.com/documentation/s3, 2018.
  * [8] IBM, “IBM Clod Object Storage,” https://cloud.ibm.com/docs/services/cloud-object-storage, 2018.
  * [9] P. Biswas, F. Patwa, and R. Sandhu, “Content level access control for openstack swift storage,” in _ACM CODASPY_ , 2015, pp. 123–126.
  * [10] X. Li, R. Li, P. P. C. Lee, and Y. Hu, “OpenEC: Toward Unified and Configurable Erasure Coding Management in Distributed Storage Systems,” in _USENIX FAST_ , 2019, pp. 331–344.
  * [11] S. A. Weil, S. A. Brandt, E. L. Miller, D. D. E. Long, and C. Maltzahn, “Ceph: A Scalable, High-performance Distributed File System,” in _USENIX OSDI_ , 2006, pp. 307–320.
  * [12] L. Militano, “Experimenting on Ceph Object Classes for Active Storage,” https://blog.zhaw.ch/icclab/experimenting-with-ceph-object-classes-for-active-storage/, 2019\.
  * [13] R. Gracia-Tinedo, J. Sampé, E. Zamora, M. Sánchez-Artigas, P. García-López, Y. Moatti, and E. Rom, “Crystal: Software-defined storage for multi-tenant object stores,” in _15th USENIX Conference on File and Storage Technologies (FAST 17)_ , 2017, pp. 243–256.
  * [14] R. Gracia-Tinedo, J. Sampé, G. París, M. Sánchez-Artigas, P. García-López, and Y. Moatti, “Software-defined object storage in multi-tenant environments,” _Future Generation Computer Systems_ , vol. 99, pp. 54–72, 2019.
  * [15] “Redis,” https://redis.io/.
  * [16] E. Gamma, R. Helm, R. Johnson, and J. M. Vlissides, _Design Patterns: Elements of Reusable Object-Oriented Software_. Addison-Wesley Professional, 1994.
  * [17] E. Bainomugisha, A. L. Carreton, T. v. Cutsem, S. Mostinckx, and W. d. Meuter, “A survey on reactive programming,” _ACM Comput. Surv._ , vol. 45, no. 4, aug 2013.
  * [18] R. A. Popa, C. M. S. Redfield, N. Zeldovich, and H. Balakrishnan, “Cryptdb: Protecting confidentiality with encrypted query processing,” in _Twenty-Third ACM Symposium on Operating Systems Principles (SOSP’11)_ , 2011, pp. 85–100.
  * [19] W3C, “XML Path Language,” https://www.w3.org/TR/xpath-30/, 2020.
  * [20] H. Shafagh, A. Hithnawi, L. Burkhalter, P. Fischli, and S. Duquennoy, “Secure sharing of partially homomorphic encrypted iot data,” in _15th ACM Conference on Embedded Network Sensor Systems (SenSys’17)_ , 2017.
  * [21] F. Vercauteren, “Optimal pairings,” _IEEE Transactions on Information Theory_ , vol. 56, no. 1, pp. 455–461, 2010.
  * [22] P. S. L. M. Barreto and M. Naehrig, “Pairing-friendly elliptic curves of prime order,” in _Selected Areas in Cryptography (SAC)_ , 2006, pp. 319–331.
  * [23] D. F. Aranha and C. P. Gouvêa, “Relic is an efficient library for cryptography,” https://github.com/relic-toolkit/relic, 2017.
  * [24] Y. H. Hwang and P. J. Lee, “Public key encryption with conjunctive keyword search and its extension to a multi-user system,” in _International conference on pairing-based cryptography_. Springer, 2007, pp. 2–22.
  * [25] A. De Caro and V. Iovino, “jpbc: Java pairing based cryptography,” in _16th IEEE Symposium on Computers and Communications, ISCC 2011_ , 2011, pp. 850–855.
  * [26] J. Sampé, M. Sánchez-Artigas, P. García-López, and G. París, “Data-driven serverless functions for object storage,” in _18th ACM/IFIP/USENIX Middleware Conference (Middleware’17)_ , 2017, pp. 121–133.
  * [27] OpenStack, “Middleware and metadata,” https://docs.openstack.org/swift/latest/development_middleware.html, 2021\.
  * [28] Google, “Guava: Google Core Libraries for Java,” https://github.com/google/guava, 2021.
  * [29] J. Sampé, P. García-López, and M. Sánchez-Artigas, “Vertigo: Programmable micro-controllers for software-defined object storage,” in _2016 IEEE 9th International Conference on Cloud Computing (CLOUD’16)_ , 2016, pp. 180–187.
  * [30] OpenStack, “Welcome to storlets’ documentation!” https://docs.openstack.org/storlets/latest/, 2020.
  * [31] L. Wang, M. Li, Y. Zhang, T. Ristenpart, and M. Swift, “Peeking behind the curtains of serverless platforms,” in _2018 USENIX Annual Technical Conference (USENIX ATC 18)_ , 2018, pp. 133–146.
  * [32] M. Seeger, “GetPut benchmarking suite,” https://github.com/markseger/getput, 2021.
  * [33] U.S. Department of Health & Human Services, “COVID-19 Reported Patient Impact and Hospital Capacity by Facility,” https://healthdata.gov/Hospital/COVID-19-Reported-Patient-Impact-and-Hospital-Capa/anag-cw7u, Apr. 2021.
  * [34] C. B. D. Newman and C. Merz, “UCI repository of machine learning databases,” https://archive.ics.uci.edu/ml/index.php, 1998.
  * [35] www.opensignal.com, “Benchmarking the global 5G user experience – October update — Opensignal,” https://www.opensignal.com/2020/10/13/benchmarking-the-global-5g-user-experience-october-update.
  * [36] www.fcc.gov, “Measuring Fixed Broadband - Tenth Report — Federal Communications Commission,” https://www.fcc.gov/reports-research/reports/measuring-broadband-america/measuring-fixed-broadband-tenth-report.
  * [37] E. Thereska, H. Ballani, G. O’Shea, T. Karagiannis, A. Rowstron, T. Talpey, R. Black, and T. Zhu, “Ioflow: a software-defined storage architecture,” in _ACM SOSP’13_ , 2013, pp. 182–196.
  * [38] I. Stefanovici, B. Schroeder, G. O’Shea, and E. Thereska, “sRoute: treating the storage stack like a network,” in _USENIX FAST’16_ , 2016, pp. 197–212.
  * [39] J. Mace, P. Bodik, R. Fonseca, and M. Musuvathi, “Retro: Targeted resource management in multi-tenant distributed systems,” in _USENIX NSDI’15_ , 2015, pp. 589–603.
  * [40] S. Shin, P. A. Porras, V. Yegneswaran, M. W. Fong, G. Gu, and M. Tyson, “Fresco: Modular composable security services for software-defined networks.” in _20th Annual Network and Distributed System Security Symposium NDSS’13_ , 2013.
  * [41] Z. István, S. Ponnapalli, and V. Chidambaram, “Software-defined data protection: Low overhead policy compliance at the storage layer is within reach!” _Proc. VLDB Endow._ , vol. 14, no. 7, pp. 1167–1174, 2021.
  * [42] F. Wang, R. Ko, and J. Mickens, “Riverbed: Enforcing user-defined privacy constraints in distributed web services,” in _16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)_ , 2019, pp. 615–630.
  * [43] L. Burkhalter, N. Küchler, A. Viand, H. Shafagh, and A. Hithnawi, “Zeph: Cryptographic enforcement of end-to-end data privacy,” in _15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21)_. USENIX Association, Jul. 2021, pp. 387–404.
  * [44] A. Vahldiek-Oberwagner, E. Elnikety, A. Mehta, D. Garg, P. Druschel, R. Rodrigues, J. Gehrke, and A. Post, “Guardat: Enforcing data policies at the storage layer,” in _Tenth European Conference on Computer Systems (EuroSys ’15)_ , 2015.
  * [45] R. Krahn, B. Trach, A. Vahldiek-Oberwagner, T. Knauth, P. Bhatotia, and C. Fetzer, “Pesos: Policy enhanced secure object store,” in _Thirteenth EuroSys Conference (EuroSys ’18)_ , 2018.


# Derived functors and Hilbert polynomials over regular local rings

Tony J. Puthenpurakal  Department of Mathematics, IIT Bombay, Powai, Mumbai
400 076<EMAIL_ADDRESS>
###### Abstract.

Let $(A,\mathfrak{m})$ be a regular local ring of dimension $d\geq 1$, $I$ an
$\mathfrak{m}$-primary ideal. Let $N$ be a non-zero finitely generated
$A$-module. Consider the functions

$t^{I}(N,n)=\sum_{i=0}^{d}\ell(\text{Tor}^{A}_{i}(N,A/I^{n}))\ \text{and}\
e^{I}(N,n)=\sum_{i=0}^{d}\ell(\text{Ext}_{A}^{i}(N,A/I^{n}))$

of polynomial type and let their degrees be $t^{I}(N)$ and $e^{I}(N)$. We
prove that $t^{I}(N)=e^{I}(N)=\max\\{\dim N,d-1\\}$.

###### Key words and phrases:

Torsion and extension functors, bounded homotopy category of projectives

###### 1991 Mathematics Subject Classification:

Primary 13D02, 13D07 ; Secondary 13A30, 13D40, 13D09

##  1\. introduction

In this paper all rings considered are commutative, Noetherian, local with
unity and all modules considered will be finitely generated. Let
$(A,\mathfrak{m})$ be a local ring of dimension $d\geq 1$, $I$ an
$\mathfrak{m}$-primary ideal in $A$ and let $L$ be an $A$-module. If $T$ is an
$A$-module of finite length then we denote by $\ell(T)$ its length. The
Hilbert-Samuel polynomial $n\mapsto\ell(L/I^{n}L)$ of $L$ with respect to $I$
is well-studied. It is known that it is of polynomial type and of degree $\dim
L$. Considerably less is known of the function
$n\mapsto\ell(\operatorname{Tor}^{A}_{i}(L,A/I^{n}))$ for $i\geq 1$. It is
known that this function is of polynomial type and of degree $\leq d-1$. There
are some results which show under certain conditions the maximal degree is
attained, see [P], [IP] and [KT]. However this function can also be
identically zero, see [P, Remark 20]. Similarly not much is known of the
function $n\mapsto\ell(\operatorname{Ext}^{i}_{A}(L,A/I^{n}))$ for $i\geq 1$.
It is known that this function is of polynomial type and of degree $\leq d-1$.
There are some results which show under certain conditions the maximal degree
is attained, see [KP], [CKST]. Even less is known of the functions
$n\mapsto\ell(\operatorname{Tor}^{A}_{i}(L,M/I^{n}M))$ and
$n\mapsto\ell(\operatorname{Ext}_{A}^{i}(L,M/I^{n}M))$ where $M$ is an
$A$-module.

Perhaps the first case to consider for these functions is when $A$ is regular.
In this case $\operatorname{projdim}N$ is finite for any $A$-module $N$.
Surprisingly we found out that the functions

$t^{I}(N,n)=\sum_{i=0}^{d}\ell(\operatorname{Tor}^{A}_{i}(N,A/I^{n}))\
\text{and}\
e^{I}(N,n)=\sum_{i=0}^{d}\ell(\operatorname{Ext}_{A}^{i}(N,A/I^{n}))$

are _easier_ to tackle. One can then work with $K^{b}(\operatorname{proj}A)$,
the homotopy category of bounded complexes of projective $A$-modules, which is
the bounded derived category of $A$. More generally let $(A,\mathfrak{m})$ be
a local ring (not necessarily regular). Let
$\mathbf{X}_{\bullet}\colon\mathbf{X}_{\bullet}^{-1}\rightarrow\mathbf{X}_{\bullet}^{0}\rightarrow\mathbf{X}_{\bullet}^{1}$
be a complex of $A$-modules. In [T, Proposition 3] it is shown that if
$\ell(H^{0}(\mathbf{X}_{\bullet}\otimes M/I^{n}M))$ has finite length for all
$n\geq 1$ then the function
$n\rightarrow\ell(H^{0}(\mathbf{X}_{\bullet}\otimes M/I^{n}M))$ is of
polynomial type. The precise degree of this polynomial is difficult to
determine (a general upper bound for the degree is given in [T, Proposition
3]).

######  1.1.

In this paper we prove a surprising result. Let $(A,\mathfrak{m})$ be a local
ring and let $K^{b}(\operatorname{proj}A)$ be the homotopy category of bounded
complexes of projective $A$-modules, Let $K^{b}_{f}(\operatorname{proj}A)$
denote the homotopy category of bounded complexes of projective $A$-modules
with finite length cohomology. Let $\mathbf{X}_{\bullet}\in
K^{b}_{f}(\operatorname{proj}A)$. We note that for any $A$-module $M$ and an
ideal $I$ we have $\ell(H^{i}(\mathbf{X}_{\bullet}\otimes M/I^{n}M))$ has
finite length for all $n\geq 1$ and for all $i\in\mathbb{Z}$. The main point
of this paper is that it is better to look at the function

$\psi_{\mathbf{X}_{\bullet}}^{M,I}(n)=\sum_{i\in\mathbb{Z}}\ell(H^{i}(\mathbf{X}_{\bullet}\otimes
M/I^{n}M)),\quad\text{for $n\geq 1$}.$

We know that $\psi_{\mathbf{X}_{\bullet}}^{M,I}(n)$ is of polynomial type say
of degree $r_{I}^{M}(\mathbf{X}_{\bullet})$. The main result of this paper is

######  Theorem 1.2.

[with hypotheses as in 1.1] Assume $M\neq 0$ and $I\neq A$. Then there exists
a non-negative integer $r_{I}^{M}$ depending only on $I$ and $M$ such if
$\mathbf{X}_{\bullet}\in K^{b}_{f}(\operatorname{proj}A)$ is non-zero then
$r_{I}^{M}(\mathbf{X}_{\bullet})=r_{I}^{M}$.

The essential reason why this happens is because
$K^{b}_{f}(\operatorname{proj}A)$ has _no_ proper thick subcategories.