1 Proof of Unlearning Deﬁnitions and Instantiation Jiasi Weng12 Shenglong Yao2 Yuefeng Du2 Junjie Huang1 Jian Weng1 and Cong Wang2

2025-04-30 0 0 1.81MB 15 页 10玖币

侵权投诉

Proof of Unlearning: Deﬁnitions and Instantiation

Jiasi Weng+1,2, Shenglong Yao2, Yuefeng Du2, Junjie Huang1, Jian Weng1, and Cong Wang2

1College of Cyber Security, Jinan University

2Department of Computer Science, City University of Hong Kong

Abstract—The “Right to be Forgotten” rule in machine learn-

ing (ML) practice enables some individual data to be deleted

from a trained model, as pursued by recently developed machine

unlearning techniques. To truly comply with the rule, a natural

and necessary step is to verify if the individual data are

indeed deleted after unlearning. Yet, previous parameter-space

veriﬁcation metrics may be easily evaded by a distrustful model

trainer. Thus, Thudi et al. recently present a call to action on

algorithm-level veriﬁcation in USENIX Security’22.

We respond to the call, by reconsidering the unlearning prob-

lem in the scenario of machine learning as a service (MLaaS), and

proposing a new deﬁnition framework for Proof of Unlearning

(PoUL) on algorithm level. Speciﬁcally, our PoUL deﬁnitions

(i) enforce correctness properties on both the pre and post

phases of unlearning, so as to prevent the state-of-the-art forging

attacks; (ii) highlight proper practicality requirements of both the

prover and veriﬁer sides with minimal invasiveness to the off-

the-shelf service pipeline and computational workloads. Under

the deﬁnition framework, we subsequently present a trusted

hardware-empowered instantiation using SGX enclave, by log-

ically incorporating an authentication layer for tracing the data

lineage with a proving layer for supporting the audit of learning.

We customize authenticated data structures to support large out-

of-enclave storage with simple operation logic, and meanwhile,

enable proving complex unlearning logic with affordable memory

footprints in the enclave. We ﬁnally validate the feasibility of the

proposed instantiation with a proof-of-concept implementation

and multi-dimensional performance evaluation.

I. INTRODUCTION

Machine learning (ML) models deployed for prediction

services are usually trained on user data, which can refer to

the current machine learning as a service (MLaaS) paradigm.

Particularly, a data owner can authorize a service provider to

train an ML model over his/her data and later offer black-box

prediction services with the trained model. But at a later time,

the data owner might withdraw the authorization, i.e., sending

a request to delete his/her data from the trained model, simply

due to regret emotion [83], [69], or deterred by privacy attacks

on trained models [66], [77], [17], [50]. Such right of data

deletion can be legally protected by privacy regulations [79],

namely “Right to be Forgotten” (RTBF) which is explicitly

stated by the European Union’s General Data Protection

Regulation (GDPR) [60] and the United States’s California

Consumer Privacy Act (CCPA) [4]. More speciﬁcally, the

U.K.’s Information Commissioner’s Ofﬁce [1] and the Federal

Trade Commission [23] recently clarify that complying with

+Work was done when the author was a Postdoc with City University of

Hong Kong.

the deletion request requires retraining the model or deleting

the model altogether.

Machine unlearning is a closely relevant concept, having a

target model forget partial training data, but previous unlearn-

ing approaches [16], [14], [32], [37], [34], [33], [52], [84]

might fail to achieve the RTBF compliance in a distrustful set-

ting. First of all, the approaches often assume an honest server.

However, the powerful server side is likely to not delete user

data in reality, which is commonly reported [28], [5], [12], and

is naturally wavering in users’ trust [72], [46]. Furthermore,

a dishonest server can also strategically evade the veriﬁcation

metrics suggested by prior unlearning approaches, by launch-

ing forging attacks [73], [67], and therefore, Thudi et al. [73]

call for action to audit unlearning, while leaving a blank space

to be ﬁlled in. Last but not least, the nature of a black-box

service manner might motivate the server to maliciously fork

multiple models, which may invalidate previous unlearning ap-

proaches as well as existing black-box veriﬁed methods [51],

[40], [70]. For instance, the server can fork an arbitrary model

(not the target model in question), and claim having deleted

data from the forking model, while still offering prediction

services using the target model which never deletes data at all.

In light of the dishonest server, which can arbitrarily deviate

from prior unlearning approaches, this work studies how to

truly implement Proof of Unlearning (PoUL) for pursuing the

RTBF compliance with end-to-end assurances, i.e., closed-

loop enforcement starting from pre-learning and prediction to

unlearning and post-prediction.

Unlearning problem. We clarify the unlearning problem

speciﬁc for the off-the-shelf ML pipeline in MLaaS. Starting

from a trained target model offering prediction services, when

a data owner requests to delete a data point, the server should

execute an unlearning process on the target model, yielding

a newly predictive model which fully eliminates the effect of

the data point in accordance to the unlearning goal of previous

efforts [16], [37], [19], [22], [14].

But the server may behave dishonestly, which may forge an

incorrect target model, or run an incorrect unlearning process

or fork an inconsistent model for new predictions. We next

deﬁne our PoUL to prevent such misbehavior with respect to

a data point deletion.

Deﬁnitions of PoUL. Here involves two sequential phases

aligned with the black-box service nature: (i) Setup phase. the

server proves that a target model in question indeed learns the

data point. (ii) Deletion phase. the server proves that a newly

predictive model is yielded by a correct unlearning process

which indeed removes the data point from the previous

arXiv:2210.11334v2 [cs.CR] 21 Oct 2022

target model. Within the deﬁnition scope, we require that the

server should simultaneously assure the correctness of the

target model, the unlearning process and the newly predictive

model, such that the data owner (as a honest veriﬁer) can be

convinced of the fulﬁllment of his/her unlearning problem.

PoUL is different from a recent excellent art [45], proof-of-

learning (PoL), which facilitates proofs for a learning process

based on the idea of re-execution. Speciﬁcally, PoL offers a

veriﬁer a document on learning trajectory for convincing him

of the truth that the learning trajectory is used to generate

a particular model with overwhelming probability. While

the PoL is easy to understand and implement, it cannot be

extended to implement the PoUL, due to different problem

statements and threat models, ﬁgured out by Thudi et al. [73].

Recent attack examples [87] can efﬁciently forge learning

trajectory to generate a fake but valid PoL proof, which

further demonstrates the difﬁculty of implementing the PoUL.

Lastly, our PoUL especially emphasizes that subsequent

prediction services should be offered by an unlearned model

as expected, which is not considered by the PoL.

To pursue practice-oriented solutions, we subsequently

highlight practicality requirements needed for our PoUL: (a)

Enabling generic models. The unlearning problem in MLaaS

can happen in various models, which requires proof tech-

niques to support generic computations involved by various

model architectures. (b) Limited invasiveness. Proof techniques

should be maximally compatible with the underlying learning

algorithms, so as to maintain the original ML services quality.

intensive ML pipeline, additional proving workloads should be

as affordable as possible. Besides the server-side requirements,

PoUL should also meet the following veriﬁer-side require-

ments, such that the data owner can enjoy predictive services

nearly as usual beyond verifying unlearning. (d) Concise proof.

Generated proofs should be short enough to ease the storage

cost of the data owner. (e) Efﬁcient veriﬁcation. Proofs should

also be cheaply veriﬁed considering a usually thin veriﬁer.

A. Solution Overview

We now present our solution roadmap to implement PoUL,

towards complying with the deletion obligation. We ob-

serve that PoUL relates to proof-based veriﬁable computation

(VC) [80], especially a line of “authenticate ﬁrst and prove

later” proof systems. Simply speaking, a data owner can

authorize her data to the server, along with a data digest

generated by authenticated data structures (ADS) [71], and

then keep track of particular zero-knowledge proofs issued

by the server, with respect to the correctness of a target

model, an unlearning process and a newly predictive model,

which are not transparent to the data owner. Yet, aware of the

mentioned practicality requirements, the line of pure crypto-

assisted proof systems [80] are not the preferred choices (see

more in Appendix A).

From another perspective, trusted execution environments

(TEEs) are quickly becoming trusted computing services

offered by dominant service providers, e.g., Alibaba Cloud [8],

IBM Cloud [43] and Microsoft Azure [2], and many

application efforts [47], [26], [30] demonstrate that TEEs can

assist the providers in performing with obligation compliance,

e.g., enforcing data usage with GDPR compliance [68], [61].

Therefore, we are naturally encouraged to instantiate PoUL

with the TEEs-backed offerings, and thereby enable native

implementation and practical deployment on the server side.

Also, we admit that recent TEEs-empowered ML works [75],

[48], [38], [74], [54], [41], [42], [86], [88], [53], [39], [11]

may help mitigate a certain issue within our PoUL, but we

need new and holistic designs tailored for proving end-to-end

RTBF compliance in MLaaS.

Our unlearning setting. We begin with Bourtoule et al.’s

efﬁcient retraining-based unlearning framework [14], towards

enabling complete deletion [35]. Speciﬁcally, the server

trains multiple chunked submodels in isolation over disjoint

shards of data, and meanwhile, each chunked submodel is

incrementally learned with non-overlapping slices of data

points (named sliced data hereafter); when one data point

is deleted, only particular submodels exactly trained on or

impacted by the data point need to be retrained, which is

therefore faster than retraining a complete model from scratch.

TEEs-capable PoUL implementation. Standing on the

unlearning setting, we incorporate ADS with Intel Software

Guard Extensions (SGX) [3], [24] on the server side, to issue

proofs in the Setup and Deletion phases previously described.

Our incorporation implies (i)an authentication layer for

tracing which sliced data are learned or unlearned, and which

chunked submodels are retrained or used to offer predictions;

and (ii)a proving layer for attesting the execution correctness

of the learning or prediction processes that exactly use

particular authenticated data or submodels.

However, it is challenging to implement the two-layer

incorporation, due to the incompatible features between our

unlearning setting and Intel SGX.

Challenge (i): Memory-Efﬁcient Authentication. In the

authentication layer, we require tracking which sliced

data impact which chunked submodels, and supporting

authenticated updates on the impacted submodels when a data

point is deleted. But both data and submodels are often large-

size and the unlearning problem might cause a large number

of submodels to be updated, which inevitably incurs large

memory footprints far beyond the original memory limitation

of SGX1. Hence, we provide a memory-efﬁcient authentication

design tailored for the traceability from the sliced data to the

updatable submodels while protecting the integrity.

Challenge (ii): Proof of Stateful Computation and Fast

Veriﬁcation. In the proving layer, the computations involving

a chain of incremental retraining processes to update affected

submodels, and subsequent prediction processes using the

newly retrained model should be attested, so that a veriﬁer

is convinced of the fulﬁllment of data deletion. Yet, the

computations are stateful, since the incremental retraining and

prediction processes require previously generated states, e.g.,

submodels, which is in conﬂict with the SGX design of pri-

marily protecting stateless computations. We extend the trust

outside the SGX’s protected memory to securely save previous

1It is about 94 MB available to applications in a widely adopted version,

and a recent release [6] supports 188 MB.

states, by typically letting the protected memory retain unique

randomnesses (named seed) respective to each submodel for

subsequent integrity checking. To reduce veriﬁcation cost, we

adopt a self-veriﬁcation strategy. Concretely, we enable the

veriﬁer to only assert that an appointed submodel (i.e., a ﬁnal

one) matching a newly produced digest yields new predictions

on a given test data, while the authenticity of all retrained

submodels prior to the appointed submodel is veriﬁed by the

enclave itself. Furthermore, in light of the need for monitoring

the correctness of subsequent prediction services, an additional

SGX-enabled auditor is considered.

In summary, we make three-fold contributions as following:

•We propose a new two-phase deﬁnition framework for

achieving PoUL, which adapts to Bourtoule et al.’s

generic unlearning algorithm (in IEEE S&P’21), and

meanwhile, prevents recent forging attacks (in USENIX

Security’22).

•Under the deﬁnition framework, we present an SGX-

capable solution with newly customized designs, by log-

ically integrating an authenticated layer for tracing the

lineage of training data with a proving layer for auditing

the correctness of model training.

•We give a proof-of-concept implementation for the SGX-

capable PoUL, and evaluate the multifaceted perfor-

mance in terms of storage cost, deletion time, learn-

ing/unlearning time and trained accuracy. The imple-

mentation code is available in https://github.com/James-

yaoshenglong/unlearning-TEE.

II. BACKGROUND

A. Machine Unlearning

Machine unlearning starts from a concept of removing

a/some training data from an already trained model [16].

According to the different understanding of the concept,

existing approaches can be roughly classiﬁed into two

groups, including approximate unlearning achieving data

deletion from parameter level [34], [33], [32], [63] and exact

unlearning achieving data deletion from algorithm level [16],

[14], [37], [19], [22]. The essential difference between the

two groups is clariﬁed by the Deﬁnition 1.

Deﬁnition 1: Let D={di} ∪ du, i ∈ {1, . . . , N}\ube a

collection of Ntraining samples. Let D−udenote a collection

of N−1training samples, namely D\du. Let DMbe the

distribution of a model that has ever been trained over Dand

then unlearned duvia a machine unlearning algorithm R. Let

Mbe the distribution of a model trained over D−u. Then

denote Ras an approximate unlearning algorithm, if the

distribution DMis approximately equal to D0

M. Otherwise,

denote Ras an exact unlearning algorithm, if the distribution

DMis exactly equal to D0

Recently, the SISA framework [14] provides an exact un-

learning method towards generic ML models, which fully

erases the effect of deleted data. It is faster than retraining

from scratch by trading storage for efﬁciency, and is followed

by many promising unlearning work [37], [19], [22].

We next introduce a server-side ML pipeline under the

SISA framework, as shown in Fig. 1. Suppose the server-side

pipeline runs over the dataset authorized by a data owner and

generates learned models, along with model checkpoints. At a

later time, it complies with a deletion request of the data owner

via unlearning. We introduce the pipeline with two parts: A)

pre-learning and prediction stages, as well as B) unlearning

and post-prediction stages. We denote N={1, . . . , n}and

S={1, . . . , s}.

Fig. 1: The server-side ML pipeline under the SISA frame-

work. Multiple dashed rectangles represent that different

Shards of data are used for incrementally training constituent

models in an Isolated manner. Within one shard, the training

data is further Sliced into disjoint data slices, where the data

slice in grey (i.e.,ds−1) inﬂuences or impacts the intermediate

submodels in grey (i.e.,ms−1and ms). All constituent models

(the last submodels) of individual shards produce predictions

that are Aggregated into ﬁnal predictions.

A. Pre-learning and Prediction Stages There are four major

operations. (a) Shard. In the ﬁrst place, the data owner’s

dataset is divided into nnon-overlapping data shards, denoted

as Dj∈[N]; (b) Isolation. Subsequently, stochastic gradient

descent (SGD)-based training algorithm is applied to train

a constituent model on each shard of data in isolation; (c)

Slice. Inside each shard, the data Djis further sliced into s

disjoint data slices, represented by Dj={dj,i}i∈[S],j∈[N],

such that data slices are incrementally added for learning,

and the produced submodels {mi}i∈[S]are saved during

learning; (d) Aggregation. The ﬁnal prediction is obtained by

aggregating the predictions provided by the constituent models

ms,j , j ∈[N]of all shards. Herein, a data slice can contain

a small set of non-overlapping data points. Note that the

impact of each data point is restricted on relatively small-size

submodels, rather than an entire model.

B. Unlearning and Post-prediction Stages On receiving the

data owner’s request of deleting one data point du∈D, the

following steps are executed: (a) ﬁnd which shards this data

point dubelongs to and which submodels it inﬂuences; (b)

locate the shard and the slice associated to du, and delete the

dufrom the slice and the submodels inﬂuenced by duwithin

the shard; (c) re-execute the incremental training processes

with the remaining data slices as pre-training.

Now we show a concrete example. We suppose the du

that will be deleted falls in the last but one slice ds−1

of Fig. 1 and the submodels ms−1and msare inﬂuenced

by the du. Guided by the above steps, the ms−1and ms

will be deleted, and subsequently, new ms−1and msare

relearned over the remaining data {d1,· · · , ds−2, ds−1\du}

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1ProofofUnlearning:DenitionsandInstantiationJiasiWeng+1,2,ShenglongYao2,YuefengDu2,JunjieHuang1,JianWeng1,andCongWang21CollegeofCyberSecurity,JinanUniversity2DepartmentofComputerScience,CityUniversityofHongKongAbstractTheRighttobeForgottenruleinmachinelearn-ing(ML)practiceenablessomeindividualda...

展开>> 收起<<

1 Proof of Unlearning Deﬁnitions and Instantiation Jiasi Weng12 Shenglong Yao2 Yuefeng Du2 Junjie Huang1 Jian Weng1 and Cong Wang2.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1 Proof of Unlearning Deﬁnitions and Instantiation Jiasi Weng12 Shenglong Yao2 Yuefeng Du2 Junjie Huang1 Jian Weng1 and Cong Wang2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: