# Data Plagiarism Index: Characterizing the Privacy Risk of Data-Copying in
Tabular Generative Models

Joshua Ward , Chi-Hua Wang , Guang Cheng Ph.D. Candidate, Department of
Statistics and Data Science, UCLA, CA, 90095. Email:
<EMAIL_ADDRESS>Scholar, Department of Statistics and Data
Science, UCLA, CA, 90095. Email<EMAIL_ADDRESS>Department of
Statistics and Data Science, UCLA, CA, 90095. Email<EMAIL_ADDRESS>
###### Abstract

The promise of tabular generative models is to produce realistic synthetic
data that can be shared and safely used without dangerous leakage of
information from the training set. In evaluating these models, a variety of
methods have been proposed to measure the tendency to copy data from the
training dataset when generating a sample. However, these methods suffer from
either not considering data-copying from a privacy threat perspective, not
being motivated by recent results in the data-copying literature or being
difficult to make compatible with the high dimensional, mixed type nature of
tabular data. This paper proposes a new similarity metric and Membership
Inference Attack called Data Plagiarism Index (DPI) for tabular data. We show
that DPI evaluates a new intuitive definition of data-copying and
characterizes the corresponding privacy risk. We show that the data-copying
identified by DPI poses both privacy and fairness threats to common, high
performing architectures; underscoring the necessity for more sophisticated
generative modeling techniques to mitigate this issue.

Key Words: Data-Copying, Trustworthy AI, Membership Inference Attack, Privacy
Auditing, Synthetic Data, Tabular Generative Models.

##  1 Introduction

Data-copying is a particularly concerning manifestation of generative models
overfitting [28, 6]. Historically, researchers have observed that deep
learning models exhibit overfitting behaviors, sometimes generating
unrealistic instances and at other times creating instances overly similar to
samples in the training dataset. While the former can be lauded as ”creative
and imaginative,” the latter poses a significant risk, threatening the
confidentiality of training data. Indeed, previous studies [3] reveal that
many prominent generative models attain high scores in terms of fidelity and
diversity by memorizing or copying real samples, which compromises their
effectiveness for privacy-sensitive applications. The issue of data-copying is
paramount in the field of tabular generative models, especially as these
models are often used in scenarios involving sensitive data and strict privacy
protocols [47]. This paper focuses on the challenge of detecting and
evaluating data-copying in tabular data generation, highlighting its critical
role in enhancing the trust and accountability of these methods.

Various paradigms have been proposed to study data-copying in generative
models, including hypothesis testing [28], non-parametric statistics [6],
Membership Inference Attacks [41], and ad-hoc similarity metrics [34, 3, 38].
Each of these approaches contributes unique insights into the phenomenon of
data-copying in tabular generative models but have some sort of drawback. For
instance, while similarity metrics used in tabular synthetic data literature
offer an understanding of the geometric relationship between training and
generated data, they lack a threat model to assess the privacy risks
associated with these geometries (see [15]). Conversely, Membership Inference
Attacks provide valuable tools for understanding privacy risks but are often
disconnected from the model overfitting literature and are challenging to
apply to the complex, high-dimensional and mixed-type distributions that are
common in tabular data applications. The disjoint nature of the data-copying
literature fails to address common practitioner questions, such as:

’To what extent does a model copy training data, and how practically
significant is this problem?’

Unfortunately, we show that the problem is substantial, as evidenced by Figure
1.

In this paper, we study data-copying in tabular generative model from the
perspective of all three of these disconnected areas (Membership Inference
Attacks, ad-hoc similarity metrics and Data-Copying measures). The goal is to
craft a principled, interpretable, and privacy orientated metric that can be
applied to tabular generative modelling. Here, we propose Data Plagiarism
Index (DPI); a theory-motivated measure of local data-copying (Section 4.1).
We argue that DPI differs from other competing metrics and show how it
provides a novel geometric perspective on the data-copying behavior of
generative models. With the proposed privacy metric DPI, we further develop a
new type of Membership Inference Attack, named DPI MIA (Section 4.2), that
bridges this data-copying measure with testable privacy risk. Our experiment
(Section 5) find that DPI MIA identifies a tendency among high-fidelity
tabular data generators to perform risky data-copying, raising privacy
concerns.

Figure 1: A t-SNE plot of Tab-DDPM’s training data with corresponding top 1%
DPI Scores in red on the Adult dataset. DPI identifies an outlier region in
the bottom right corresponding to an extreme privileged class (married, white,
middle aged, high capital gains, private industry, respondents making $>$50k
in income). This provides evidence that Tab-DDPM copies the training data of
outlier and privileged classes, creating serious fairness concerns for
practitioners who use synthetic data in their downstream machine learning
tasks. See Sec. 5.3 for detailed discussions.

Furthermore, our empirical evidence (Figure 1) reveals that tabular generative
models disproportionately favor certain privileged sub-populations within the
synthetic sample of the classic Adult dataset, raising serious fairness
concerns when practitioners use synthetic data in downstream machine learning
tasks. This troubling finding underscores that the proposed Data Plagiarism
Index (DPI) is not merely a technical curiosity but a critical issue that can
compromise both the privacy and fairness of tabular generative models.

Overall, we summarize our contribution to the Trustworthy Generative Modeling
literature as follows:

  1. 1.

We propose a novel privacy measure called Data Plagiarism Index (DPI) and a
corresponding Membership Inference Attack called DPI MIA that measures the
privacy risk of synthetic tabular data from data-copying.

  2. 2.

We provide empirical evidence (Figure 4) that DPI identifies a positive
correlation between tabular generative models’ utility and privacy risks.

  3. 3.

We provide empirical evidence (Figure 1) that reveals that Tab-DDPM [23]
drastically copies the source training data of privileged sub-classes,
creating a source of structural unfairness in the synthetic data.

  4. 4.

We show (Figure 4, Table 1) that DPI MIA can identify a different kind of
data-copying undetectable by existing Membership Inference Attacks with
comparable threat performance, providing a new way to deploy privacy attacks
to audit synthetic data privacy.

##  2 Related Work

In this section, we review three major literature to measure the overfitting
and data-copying phenomenon of tabular generative models.

###  2.1 Measure Data-Copying in Generative Models

Generative models’ data-copying in the literature is identified when synthetic
data is excessively similar to training samples [28]. This is typically
evaluated using a reference dataset, sampled from the same distribution as the
training dataset. The common method involves an ”appropriate distance
function” to check whether synthetic data is closer to the training data or
the reference data [34]. [28] for example focuses on identifying a suitable
distance function to determine whether a synthetic dataset or a reference
dataset is closer to the training dataset, thus testing if generative models
exhibit data-copying. They devised a non-parametric method that divides the
instance space into cells, tests each cell individually, and combines the
results to understand the overall degree of data-copying. This concept
inspired our more sophisticated data-copying measure (See Section 3.1). [6]
introduces a more advanced data-copying test, capable of detecting data-
copying behaviors not identified by [28]. Both of these studies however have
limitations in high-dimensional complex distributions and also do not evaluate
data-copying from a privacy perspective. DPI is more practical and accurately
captures the degree of local data-copying, aiding in the assessment of
synthetic data privacy risks (See Fig 1).

###  2.2 Similarity Metrics between Real and Synthetic Data

A variety of ad-hoc metrics have been proposed to evaluate the privacy of
tabular synthetic data from a model overfitting perspective. Broadly speaking,
these metrics focus on determining the level of similarity between the
training and synthetic datasets ideally hoping to find that the generated data
is in a ’Goldilocks’ zone: not too similar to the training data, but also not
too dissimilar. These metrics will often be posed as a comparison between the
training and a reference set and training and synthetic sets creating a sort
of ’Null Distribution’ in which to test privacy.

A common example of an often used similarity metric is Distance to Closest
Record (DCR) [31, 27, 46, 51, 16, 25] where for each training point the
distance to its closest neighbor in the synthetic dataset is compared with the
distance of the closest neighbor in the reference dataset. Another is
Identical Matching Score [1, 2, 27] which compares the proportion of identical
records in the training and synthetic observations.

There are a variety of problems with this style of privacy evaluation. The
first is that these similarity metrics do not actually guarantee nor are they
evaluated by any idea of privacy protections against some sort of attack. For
example, passing or failing a DCR or IMS test does not provide any information
for how well a privacy attack may or may not do. Secondly, posing privacy as a
hypothesis testing problem is a cardinal Statistics sin in that if the null
hypothesis is: ”the synthetic data are private” and the alternative is: ”the
synthetic data are not private”, passing the test does not imply confirmation
of the null, only that there is a failure to find sufficient evidence in which
to reject the null [7]. However, while not being theoretically motivated,
these metrics do provide an intuitive tool to study the geometric
relationships between the training and synthetic datasets. Technically, DPI
can be classified as a similarity metric and used in this way but these
problems motivate DPI to adopt a Membership Inference Attack paradigm to
overcome these dubious privacy interpretations.

###  2.3 Membership Inference Attacks for Generative Models

Membership Inference Attacks have traditionally been studied in a supervised
learning context and only relatively recently have become applied to
generative models. Here, the goal of the attack is to determine whether some
sample of test data $x^{*}\in X^{*}$ was used in the training of the model
based on some information about that model [37]. The scenario of what
information is available for an attacker is called the threat model to which
there are a variety of identified contexts for generative model MIAs. These
include black box attacks [17, 18, 8] in which only generated synthetic data
is available, white box attacks in which both synthetic data and the internals
of a model are known, and calibrated (also called shadow) attacks in which
both a synthetic dataset and then a reference dataset from the same or similar
distribution as the training set are given [8, 17, 41]. Most attacks generally
fall into the black box and calibrated paradigms as white box attacks are
usually specific to the model architecture in question [36]. The value of MIAs
is that they provide a tangible, practical scenario in which to study privacy
risks. We will later frame DPI as an MIA in order to study how identifying
local data-copying corresponds to privacy leakage.

##  3 Preliminaries

###  3.1 Formal definition of Data-Copying

We first introduce a formal definition of data-copying motivated by [28] to
provide theoretical context for Data Plagiarism Index. Given a data
distribution $\mathbb{P}$ and a region $C$, consider the following probability
measure: $\mathbb{P}|_{C}(A)\equiv\mathbb{P}(A\cap C)/\mathbb{P}(C)$ for all
measurable set $A$. Let $R$ denote the distribution of reference data points
and $S$ denote the distribution of synthetic data points.

Given a neighborhood $D(x)$ of target data point $x$, define a one-dimensional
distribution by $L(R)\equiv I(R\in D(x))$ and $L(S)\equiv I(S\in D(x))$ to
denote separately the event of the reference data distribution and synthetic
data distribution belonging to the neighborhood $D(x)$. By definition,
$L(R)\sim R|_{D(x)}$ and $L(S)\sim S|_{D(x)}$

Define $\Delta(R,S)=P(B>A|B\sim L(S),A\sim L(P)$ to be the event that the
synthetic data points have a greater probability in belonging to neighborhood
$D(x)$ than the reference data points.

In the spirit of Definition 2.1 of [28], we define a generative model as data-
copying a training data point $x$, if there exists a neighborhood $D(x)$ of
$x$ such that the synthetic data distribution $S$ is systematically closer to
the training data point $x$ than the reference data distribution $R$, in the
sense that

$\Delta(R|_{D(x)},S|_{D(x)})<\frac{1}{2}$

See Figure 2(a) as an example.

###  3.2 Distance to Closest Records (DCR)

The Distance to Closest Records (DCR) technique was developed to identify
identical matches between synthetic and training data [31, 27]. However, it is
essential to note that detecting identical matches and identifying data-
copying are distinct tasks. While distance measures are appropriate for
finding identical matches, they are not as effective for detecting data-
copying, which is more appropriately viewed as a proportional measure. As
discussed in Section 3.2 of [34], a DCR of zero signifies an identical match,
but a non-zero DCR does not capture the extent of personal information
disclosure. This inherent flaw renders DCR an unsuitable measure of synthetic
data privacy, as it does not accurately assess privacy risk. Our proposed Data
Plagiarism Index (DPI) provides a more effective metric for synthetic data
privacy by quantifying privacy risk. We utilize DPI to construct a Membership
Attack, whose results reveal the privacy risks of synthetic data. See Section
4.2.

###  3.3 Membership Inference Attacks as Privacy Auditors

Membership Inference Attacks (MIA) for synthetic data aim to determine if a
given sample was a member of the original training set used to train a
generative model. Consider a random variable $X$ defined on the domain
$\mathcal{X}$, following a probability distribution $p_{X}(X)$. Let
$D_{train}$ represent a training dataset consisting of independently sampled
observations from $p_{X}(X)$. A generative model $G$ is then trained on
$D_{train}$ and used to produce a synthetic dataset $D_{syn}$. An attacker
model, $\mathcal{A}:X\to{0,1}$, has access to the synthetic dataset $D_{syn}$,
a test data point $x^{*}$ drawn from the same distribution as $X$, and
depending on the threat model, potentially other information. The attacker’s
objective is to determine whether the test point $x^{*}$ belongs to the
original training set $D_{train}$. An ideal attacker would output
$\mathcal{A}(x^{*})=1$ if $x^{*}\in D_{train}$, and $0$ otherwise. By
considering privacy in this framework, MIAs allow for the practical evaluation
of the risk of synthetic data release, relative to an adversarial scenario
[37].

In this paper, we study a special case of Membership Inference Attacks in
which the attacker has access to an additional reference dataset $D_{ref}$
sampled from same distribution as $D_{train}$ but not used in the training of
$G$. There are a variety of both practical and theoretical reasons for the
inclusion of $D_{ref}$ in the attack. First, $D_{ref}$ represents a worse-case
scenario in which the attacker has access to the most information possible in
which to build an attack which makes this situation important to study from a
conservative, privacy conscious data publisher’s perspective. Second, it is a
real scenario that particularly tabular-orientated data publishers face in
that $D_{ref}$ can be a leaked dataset, historic data, data from a competitor,
or even a dataset built from publicly available data. Lastly, the inclusion of
$D_{ref}$ is theoretically motivated from the growing body of literature
involved with testing for data-copying in a generative model in that in order
most frameworks contextualize model miss-specification between $D_{train}$ and
$D_{syn}$ as being relative to a holdout dataset [28, 6, 34].

##  4 Measuring Data-Copying Misbehavior

Figure 2: Data Plagiarism Index (DPI): We propose a novel privacy metric named
Data Plagiarism Index (DPI). For each target data point (black point), we
calculate the Data Plagiarism Index $\rho$ by first construct a k-nearest
neighborhood (blue circle) around the target data point on the space with
reference data points (green points) and synthetic data points (red points).
The Data Plagiarism Index $\rho$ is defined simply as the ratio of number of
synthetic data points to the number of reference data points. See Sec. 4.1 for
whole details.

###  4.1 Data Plagiarism Index (DPI)

We propose a novel privacy metric called Data Plagiarism Index (DPI), as
illustrated in Figure 2. For each training data point $x$, we calculate the
Data Plagiarism Index $\rho$ by first constructing a K-Nearest Neighborhood
$D(x)$ around $x$ on the space with reference data points and synthetic data
points. The Data Plagiarism Index $\rho$ is defined simply as the ratio of
number of synthetic data points to the number of reference data points; that
is

$\rho(x)\equiv\frac{\sum_{x_{i}\in D(x)}I(x_{i}\in S)}{\sum_{x_{i}\in
D(x)}I(x_{i}\in R)}$ (1)

The DPI ranges from 0 to infinity, capturing a spectrum of data generation
scenarios:

  * •

DPI = 0: Indicates no synthetic data points in the neighborhood, suggesting
potential under-fitting by the generative model.

  * •

DPI = 1: Represents an equal number of synthetic and reference data points,
implying no data plagiarism or under-fitting, signifying a balanced data
generation process.

  * •

DPI $>$ 1: Highlights a greater presence of synthetic data points compared to
reference data points, with increasing values pointing towards significant
data plagiarism.

This comprehensive range allows the DPI to effectively capture various data
generation scenarios, providing critical insights into the quality and privacy
of synthetic datasets.

We provide 3 toy examples to help better understand how to interpret DPI
values. In each example, consider the $K=10$ nearest neighborhood for the
target data point $x$, denoted by $D(x)=\\{x_{1},\cdots,x_{n}\\}$. Each
element $x_{i}$ in the neighborhood may come from the synthetic dataset $S$ or
reference dataset $R$:

Toy Example 1 (Data Plagiarism, Figure 2.(a)). Say 8 elements come from the
synthetic dataset and 2 elements come from the reference dataset. Then the
Data Plagiarism Index $\rho(x)=8/2=4$, which means the number of synthetic
data points is 4 times that of the reference data points! This marks serious
data-copying behavior from that generative model.

Toy Example 2 (Generator Under-fitting, Figure 2.(b)). In this situation, say
2 elements come from the synthetic dataset and 8 elements from the reference
dataset. Then the Data Plagiarism Index $\rho(x)=2/8=1/4$, which means the
number of synthetic data points is 25% of that of the reference data points!
This marks little data-copying behavior, but also suggests a potential
underfitting issue around the target data point $x$.

Toy Example 3 (Data-Copying Free, Figure 2.(c)). Lastly, say there are 5 items
from the synthetic dataset and 5 from the reference dataset. The Data
Plagiarism Index is then $\rho(x)=5/5=1$, meaining the number of synthetic
data points is equal to the number of reference data points! This marks no
data plagiarism and no underfitting behavior around the target data point $x$.

In summary, the Data Plagiarism Index offers a robust and intuitive metric for
evaluating the balance between synthetic and reference data points within a
specified neighborhood around a target data point. By calculating the ratio of
synthetic to reference data points, the DPI effectively highlights critical
instances of data plagiarism, under-fitting, or a balanced data generation
process. This metric is invaluable for rigorously assessing the performance of
generative models, ensuring data integrity, and proactively identifying
potential issues in synthetic data generation.

Figure 3: Data Plagiarism Index Membership Inference Attack (DPI MIA) See Sec.
4.2 for full details.

###  4.2 Data Plagiarism Membership Inference Attack

While the Data Plagiarism Index defined at Equation (1) provides insight into
the local behavior of generative models, on its own it does not characterize
the actual privacy risk of data-copying in tabular generative models. We
therefore show that a Membership Inference Attack can be derived from DPI
which is designed to measure and then attack the local data-copying of
generative models to evaluate the privacy risk.

Note that, in the literature of similarity metrics (Sec. 2.2), only the
training dataset $D_{train}$ is compared to the synthetic $D_{syn}$ and
reference $D_{ref}$ sets. In the MIA paradigm however (Sec. 2.3), a fourth
holdout dataset $D_{holdout}$ is taken and combined with the training dataset
post generator training: $X=D_{train}\cup D_{holdout}$. The goal of an
attacker $\mathcal{A}(x)$ is to effectively discriminate which set each record
$x\in X$ originated from.

The Membership Inference Attack based on the Data Plagiarism Index can divided
into three steps (See Figure 3):

Step 1: Prepare 4 Datasets. In the initial step, four distinct datasets are
prepared to facilitate an attack construction. The foundation begins with the
original dataset (denoted in black), which is divided into 3 equal sized sub-
sets: the Training Dataset (blue), the Holdout Dataset (Yellow) and the
Reference Dataset (green). The Training Dataset is used to train the
generative model, which subsequently generates the Synthetic Dataset (red). In
parallel, the Holdout Dataset serves as an independent test set, deliberately
excluded from the training phase.

Step 2: Compute DPI Values. The second step involves the computation of the
Data Plagiarism Index (DPI) values defined at (1) for each data point within
both the Holdout and Training datasets. This identifies data-copying in the
local neighborhoods of test points from both datasets. The intuition here is
that scores for test points from the Training set should theoretically be
higher than the Holdout set if a model is vulnerable to copying data.

Step 3: Perform MIA for Each Test Point In Step 3, a Membership Inference
Attack (MIA) is executed to evaluate the privacy risk associated with a
specific target data point. This uses the DPI score of the target data point,
which is compared against a predefined threshold $c$. The attack can be
written as:

$\mathcal{A}(\cdot)=I(\rho(\cdot)>c),$ (2)

where $\mathcal{A}$ denotes the attack function, $\rho(\cdot)$ signifies the
DPI value, and $I$ is an indicator function assessing if the DPI surpasses the
threshold $c$. Should the DPI value of the target data point exceed $c$, it
indicates that the data point is likely to have been part of the training
data, thereby exposing a potential privacy breach. In practice, MIAs are often
benchmarked using AUCROC and so the choice of $c$ is largely irrelevant. Our
implementation chooses $c$ as the median of $\rho(x)$ for $x$ for all test
data.

The proposed DPI MIA defined at Equation (2), though straightforward, is a
fast and easily interpretable attack, well-suited for auditing privacy in
high-dimensional, mixed-type datasets. Indeed, as it only uses a K-Nearest
Neighbor Search, it can be ran with linear or logarithmic time complexity (see
[14], [21]). Moreover, DPI MIA is compatible with various definitions of
distance, making it versatile to many specific applications.

##  5 Results

###  5.1 Experiment Setup

We are interested in studying how DPI compares with other Membership Inference
Attacks, to what extent different tabular data generator architectures copy
data, and if there are trends in the kind of data copied. To investigate these
research questions, we benchmark a variety of model architectures and MIAs on
the Adult Census dataset [5]. We provide descriptions of each model and MIA in
appendix B and C respectively. In each experiment, Adult is randomly split
into 3 equal sized training, holdout and reference sets where the generated
synthetic size is also equal to these set. We replicate each experiment 5
times and visualize or report the means and standard deviations of the
measures of interest where applicable.

For DPI, $K$ has to be chosen as a hyperparameter and for data visualization
purposes we plot the best performing DPI attack (Using L2 distance and
$K$=20). We refer to appendix LABEL: for an ablation study of Section 5.4
containing plots with various distance metrics and $K$ levels but in practice,
DPI is fairly stable in its results regardless of $K$ and we observed no
extreme changes in behavior based on these hyperparameters.

Figure 4: Classifier AUCROC, Maximum Mean Discrepancy, and Wasserstein
Distance plotted with corresponding DPI MIA AUCROC for various common
architectures. Interestingly, Bayesian Network, Adversarial Random Forest, and
Tab-DDPM outperform other models in these performance metrics but have higher
privacy risk. See Sec. 5.2 for full details.

###  5.2 Data-Copying in Tabular Data Generators

We first wish to confirm that there is a privacy risk to data copying in
common tabular generators. Here, we benchmark a wide range of tabular
generator strategies including: CTGAN and TVAE [45], Normalizing Flows (NFlow)
[12], Bayesian Network (BN) [4], Adversarial Random Forests (ARF) [44], Tab-
DDPM [23], PATEGAN [49], and Ads-GAN [48]. We evaluate these models on several
metrics of synthetic data quality: the Maximum Mean Discrepancy between the
training and generated data (lower is better), the Wasserstein distance
between the marginals of the training and generated data (lower is better),
and finally the AUCROC of an XGBoost [9] classifier trained on the synthetic
set and tasked to predict on a holdout set (higher is better). We deploy the
DPI MIA attack as described in Section 4.2 and report its AUCROC.

We visualize the mean values of utility metrics plotted against the AUCROC of
DPI MIA in Figure 4. Very interestingly, we observe that there is a clear
trend between model performance and privacy risk. This suggests that data-
copying could be a reason for why these models perform better, but additional
research would need to be conducted to see if this is a causal or correlative
relationship.

Figure 5: MIA AUCROC Benchmarks by Training Set Size on Tab-DDPM. This shows
that DPI MIA is more effective than other existing MIAs described at Sec. 2.3.
See Sec. 5.4 for full details.

###  5.3 Properties of Training Data with High DPI Scores

We also investigated the training data egregiously copied according to DPI.
Here, we identified the top 1% highest scored training data based on synthetic
data generated by Tab-DDPM [23] as it is widely used as a benchmark in the
current tabular generation literature [39, 22, 50]. We visualize these data in
Figure 1 as a t-SNE plot [42] with the top 1% highly scored indexes by DPI in
red. Worryingly, DPI identifies an outlier region of the distribution as being
subject to this extreme top percentile data-copying (the bottom right of the
plot). When analyzing these observation themselves, we found that an extreme
majority were all examples of married, white, middle aged, high capital gains,
private industry, respondents making ¿50k in income. In the algorithmic
fairness literature that often uses Adult in benchmarking, this is considered
to be a minority but very privileged class [30]. This suggests that not only
is there a technical and privacy concern with data-copying, but it could also
exacerbate unfairness.

Figure 6: Distance Based Metrics/ MIAs of Overfitting vs DPI. DCR and GAN
Leaks Calibrated evaluate overfitting based on a difference in relative
distances whereas DPI evaluates data-copying based on the larger local
neighborhood. This means that DPI evaluates data-copying differently than
competing methods, explaining why predictions scores are not highly correlated
(See Table 1). See Sec. 6.2 for full details.

###  5.4 Benchmarking the Privacy Risk of DPI

Lastly, we evaluate DPI in relation to other MIAs in order to understand its
efficacy as an MIA strategy. We evaluate the black box attacks of MC [18], and
GAN Leaks [8] as well as the calibrated attacks of LOGAN [17], GAN Leaks
Calibrated [8] and DPI. We also benchmarked DOMIAS [41], but we found that its
density estimation failed to converge and its results were always the
equivalent of random guess and therefore we do not formally report it. Again,
we evaluate these methods on Tab-DDPM [23]. In Figure 5, we display the
results for each of these methods across various $D_{train}$/ $D_{ref}$/
$D_{syn}$ sizes. For simplicity, each dataset is equal in size to its other.

Table 1: AUCROC for DPI and GAN Leaks Calibrated with Corresponding Pearson Correlations for the Predicted Scores. This tables shows that the proposed DPI identifies different types of data-copying than the one identified by the existing MIA attack. See Sec. 5.4 for whole details. Model | Metric
---|---
DPI MIA | GAN Leaks CAL | $r$
Tab-DPDM | 0.510±0.004 | 0.507±0.003 | 0.404±0.012
BN | 0.532±0.005 | 0.623±0.000 | 0.268±0.020
ARF | 0.520±0.000 | 0.524±0.001 | 0.339±0.006
AdsGAN | 0.503±0.003 | 0.501±0.003 | 0.467±0.039
CTGAN | 0.504±0.003 | 0.501±0.005 | 0.444±0.063
NFlow | 0.501±0.006 | 0.500±0.000 | 0.482±0.023
PATEGAN | 0.503±0.003 | 0.502±0.003 | 0.516±0.018
TVAE | 0.505±0.005 | 0.502±0.003 | 0.466±0.023

Overall, DPI is competitive with other Membership Inference Attacks compatible
with these data, dominating at most testing sizes. Interestingly, GAN Leaks
Calibrated performs similarly or better than DPI. However, GAN Leaks
Calibrated scores test data very differently than DPI, being based on a
difference in the relative distances of the closest synthetic and reference
points. In Table 1 we show that for various models, while the performance of
GAN Leaks Calibrated and DPI can differ, the Pearson Correlation between their
scores is relatively low. This implies that while these measures are
correlated, DPI is picking up on its specific data-copying definition. Indeed,
the motivation of this work is not to create a State of the Art Membership
Inference Attack for all architectures, but rather to characterize the unique
risk DPI implies.

##  6 Discussions

###  6.1 Implications for Privacy and Fairness in Synthetic Data

Data Plagiarism Index provides evidence that popular tabular generative models
can exhibit risky data-copying behavior. This includes leaking information and
favoring specific sub-class outliers in the distribution of the training data.
Thus, DPI can be used as a tool to audit and study model behavior. It should
be noted however, that while DPI can show synthetic data are not private, it
cannot prove the opposite: that particular synthetic data are private. For
example, different MIAs may have various levels of success if their method
targets different attributes of the synthetic data. This is proved by Table 1
where DPI and GAN Leaks Calibrated predicted scores, while correlated, were
not perfectly aligned.

On top of model auditing, DPI can be connected to Differential Privacy
applications [13]. Here, DPI can be used to evaluate the practical lower bound
of the privacy parameter $\epsilon$. For example, one approach is to select a
pair of neighboring training datasets $D_{1}$ and $D_{2}$ and produce
corresponding synthetic datasets $\widetilde{D}_{1}$ and $\widetilde{D}_{2}$
with a generative model. With DPI, we can then create corresponding data
copying score distributions to find a decision rule that, given an unknown
synthetic dataset $\widetilde{D}$, identifies whether its source was $D_{1}$
or $D_{2}$. If the decision rule’s true positive rate is $\alpha$ and the
false negative rate is $\beta$, based on the remark after Theorem 1 in [19],
the privacy budget’s lower bound can be expressed as
$\epsilon\geq\log\max\left\\{\frac{\alpha}{1-\beta},\frac{\beta}{1-\alpha}\right\\}$.
This approach quantifies the minimum differential privacy level that the
generative model upholds.

###  6.2 Methodological Differences in DPI

DPI provides a new geometric definition for data-copying in the context of an
available reference set and uniquely attacks this attribute relative to other
MIAs. In Figure 6, we show a variety of scenarios in which hypothetical test
data points are plotted with their closest synthetic and reference set
neighbors. We show that under the Distance to Closest Record (DCR) metric and
GAN Leaks Calibrated MIA [8] (which in many respects is the MIA version of
DCR) understanding of data-copying, certain scenarios would be classified
differently where they would label a positive instance of overfitting based on
extreme differences in the distances of the nearest synthetic and reference
points whereas DPI labels it based off of extreme differences in proportions.
Thus, DPI evaluates data-copying in a fundamentally different way than DCR/
GAN Leaks Calibrated and provides additional insight into how the training and
synthetic data are distributed.

###  6.3 Challenges in Tabular Data Generation

A key challenge of generative modelling with tabular data is the unstructured,
high dimensional, mixed type nature of most datasets [45]. This poses a
challenge for newer results on model data-copying and Membership Inference
attacks that focus on density estimation. [6] for example proposes a scheme of
comparing local densities of training data and synthetic data but does not
frame their work from an MIA perspective. Similarly, they provide a proof that
their method is not effective on non-smooth distributions that are
characteristic in the tabular domain. DOMIAS [41] evaluates overfitting as an
MIA by comparing a test point to the probability densities of the synthetic
and reference distributions. They propose two options for estimating these
densities in using a Gaussian Kernel Density Estimator and a deep learning
method called Block Neural Autoregressive Flow (BNAF) [11]. We found however
that these methods have difficulty converging with high dimensional, mixed
type datasets. Indeed, the highest dimensional tabular dataset that was
benchmarked in DOMIAS was a private healthcare dataset that when one-hot-
encoded was 35 columns. Adult when similarly pre-processed is 109 columns. All
of our experiments with DOMIAS failed to converge, leaving its results as
being the equivalent of random guess. Indeed the authors note a limitation of
the work is its reliance on BNAF in that it can take several hours to train.
This motivates this paper to consider a computationally easier paradigm of
analyzing local neighborhoods around test points.

##  7 Conclusion and Future Work

In this paper, we propose a novel measure of data-copying and connect it to
the Membership Inference Attack literature for tabular generative models. This
allows the unique study of how local data-copying contributes to risks in the
trustworthiness of these generators. Models that perform well in generating
data with high measures of utility tend to copy training data more than models
of a lower quality and thus have higher privacy risk profiles. Similarly, we
have shown that Tab-DDPM, a highly cited and studied architecture egregiously
copies outlier training data of privileged sub-classes in a widely used
fairness benchmarking dataset. This indicates that data-copying can effect a
variety of concepts, such as fairness, used to evaluate the trustworthiness of
generative models.

Data Plagiarism Index motivates a variety of directions for future work. The
disparate nature of the data-copying literature necessitates a broader
theoretical framework in which to connect data-copying to privacy. Similarly,
this work has shown that data-copying can affect different axis’ in which to
evaluate the trustworthiness of models. It would be interesting to further
explore if it also effects other aspects of Trustworthy AI such as robustness,
interpretability, and reliability. Lastly, DPI can be applied to Differential
Privacy Auditing where it can be used to evaluate sharper privacy lower
bounds.

## References

  * [1] Mostly AI.  Truly anonymous synthetic data – evolving legal definitions and technologies (part ii).  2020\.
  * [2] Mostly AI.  How to implement data privacy? a conversation with klaudius kalcher.  2021\.
  * [3] Ahmed Alaa, Boris Van Breugel, Evgeny S Saveliev, and Mihaela van der Schaar.  How faithful is your synthetic data? sample-level metrics for evaluating and auditing generative models.  In International Conference on Machine Learning, pages 290–306. PMLR, 2022.
  * [4] Ankur Ankan and Abinash Panda.  pgmpy: Probabilistic graphical models using python.  In Proceedings of the Python in Science Conference, SciPy. SciPy, 2015.
  * [5] Barry Becker and Ronny Kohavi.  Adult.  UCI Machine Learning Repository, 1996.  DOI: https://doi.org/10.24432/C5XW20.
  * [6] Robi Bhattacharjee, Sanjoy Dasgupta, and Kamalika Chaudhuri.  Data-copying in generative models: a formal framework.  In International Conference on Machine Learning, pages 2364–2396. PMLR, 2023.
  * [7] George Casella and Roger Berger.  Statistical Inference.  Duxbury Resource Center, June 2001.
  * [8] Dingfan Chen, Ning Yu, Yang Zhang, and Mario Fritz.  Gan-leaks: A taxonomy of membership inference attacks against generative models.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, CCS ’20. ACM, October 2020.
  * [9] Tianqi Chen and Carlos Guestrin.  Xgboost: A scalable tree boosting system.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, page 785–794, New York, NY, USA, 2016. Association for Computing Machinery.
  * [10] Yinan Cheng, Chi-Hua Wang, Vamsi K Potluru, Tucker Balch, and Guang Cheng.  Downstream task-oriented generative model selections on synthetic data training for fraud detection models.  arXiv preprint arXiv:2401.00974, 2024.
  * [11] Nicola De Cao, Ivan Titov, and Wilker Aziz.  Block neural autoregressive flow.  35th Conference on Uncertainty in Artificial Intelligence (UAI19), 2019.
  * [12] Conor Durkan, Artur Bekasov, Iain Murray, and George Papamakarios.  Neural spline flows, 2019.
  * [13] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer, 2006.
  * [14] Jerome H. Friedman, Jon Louis Bentley, and Raphael Ari Finkel.  An algorithm for finding best matches in logarithmic expected time.  ACM Transactions on Mathematical Software, 3(3), 7 1976.
  * [15] Georgi Ganev and Emiliano De Cristofaro.  On the inadequacy of similarity-based privacy metrics: Reconstruction attacks against ”truly anonymous synthetic data”, 2023.
  * [16] Morgan Guillaudeux, Olivia Rousseau, Julien Petot, Zineb Bennis, Charles-Axel Dein, Thomas Goronflot, Matilde Karakachoff, Sophie Limou, Nicolas Vince, Matthieu Wargny, and Pierre-Antoine Gourraud.  Patient-centric synthetic data generation, no reason to risk re-identification in the analysis of biomedical pseudonymised data.  05 2022.
  * [17] Jamie Hayes, Luca Melis, George Danezis, and Emiliano De Cristofaro.  Logan: Membership inference attacks against generative models.  Proceedings on Privacy Enhancing Technologies, 2019:133 – 152, 2017.
  * [18] Benjamin Hilprecht, Martin Härterich, and Daniel Bernau.  Monte carlo and reconstruction membership inference attacks against generative models.  Proceedings on Privacy Enhancing Technologies, 2019:232 – 249, 2019.
  * [19] Florimond Houssiau, James Jordon, Samuel N Cohen, Owen Daniel, Andrew Elliott, James Geddes, Callum Mole, Camila Rangel-Smith, and Lukasz Szpruch.  Tapas: a toolbox for adversarial privacy auditing of synthetic data.  arXiv preprint arXiv:2211.06550, 2022.
  * [20] Din-Yin Hsieh, Chi-Hua Wang, and Guang Cheng.  Improve fidelity and utility of synthetic credit card transaction time series from data-centric perspective.  arXiv preprint arXiv:2401.00965, 2024.
  * [21] International Computer Science Institute and S.M. Omohundro.  Five Balltree Construction Algorithms.  Technical report (International Computer Science Institute). International Computer Science Institute, 1989.
  * [22] Jayoung Kim, Chaejeong Lee, and Noseong Park.  STasy: Score-based tabular data synthesis.  In The Eleventh International Conference on Learning Representations, 2023.
  * [23] Akim Kotelnikov, Dmitry Baranchuk, Ivan Rubachev, and Artem Babenko.  Tabddpm: Modelling tabular data with diffusion models, 2022.
  * [24] Yuantong Li, Chi-Hua Wang, and Guang Cheng.  Online forgetting process for linear regression models.  In International Conference on Artificial Intelligence and Statistics, pages 217–225. PMLR, 2021.
  * [25] Tongyu Liu, Ju Fan, Guoliang Li, Nan Tang, and Xiaoyong Du.  Tabular data synthesis with generative adversarial networks: design space and optimizations.  The VLDB Journal, 33(2):255–280, aug 2023.
  * [26] Yucong Liu, Chi-Hua Wang, and Guang Cheng.  On the utility recovery incapability of neural net-based differential private tabular training data synthesizer under privacy deregulation.  arXiv preprint arXiv:2211.15809, 2022.
  * [27] Pei-Hsuan Lu, Pang-Chieh Wang, and Chia-Mu Yu.  Empirical evaluation on synthetic data generation with generative adversarial network.  In Proceedings of the 9th International Conference on Web Intelligence, Mining and Semantics, WIMS2019, New York, NY, USA, 2019. Association for Computing Machinery.
  * [28] Casey Meehan, Kamalika Chaudhuri, and Sanjoy Dasgupta.  A three sample hypothesis test for evaluating generative models.  In International Conference on Artificial Intelligence and Statistics, pages 3546–3556. PMLR, 2020.
  * [29] Matthieu Meeus, Florent Guepin, Ana-Maria Creţu, and Yves-Alexandre de Montjoye.  Achilles’ Heels: Vulnerable Record Identification in Synthetic Data Publishing, page 380–399.  Springer Nature Switzerland, 2024.
  * [30] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan.  A survey on bias and fairness in machine learning, 2022.
  * [31] Noseong Park, Mahmoud Mohammadi, Kshitij Gorde, Sushil Jajodia, Hongkyu Park, and Youngmin Kim.  Data synthesis based on generative adversarial networks.  arXiv preprint arXiv:1806.03384, 2018.
  * [32] Noseong Park, Mahmoud Mohammadi, Kshitij Gorde, Sushil Jajodia, Hongkyu Park, and Youngmin Kim.  Data synthesis based on generative adversarial networks.  Proceedings of the VLDB Endowment, 11(10):1071–1083, June 2018.
  * [33] Elizabeth S Parker, Larry Cahill, and James L McGaugh.  A case of unusual autobiographical remembering.  Neurocase, 12(1):35–49, 2006.
  * [34] Michael Platzer and Thomas Reutterer.  Holdout-based empirical assessment of mixed-type synthetic data.  Frontiers in big Data, 4:679939, 2021.
  * [35] Zhaozhi Qian, Bogdan-Constantin Cebere, and Mihaela van der Schaar.  Synthcity: facilitating innovative use cases of synthetic data in different data modalities, 2023.
  * [36] Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, Yann Ollivier, and Hervé Jégou.  White-box vs black-box: Bayes optimal strategies for membership inference.  In International Conference on Machine Learning, pages 5558–5567. PMLR, 2019.
  * [37] R. Shokri, M. Stronati, C. Song, and V. Shmatikov.  Membership inference attacks against machine learning models.  In 2017 IEEE Symposium on Security and Privacy (SP), pages 3–18, Los Alamitos, CA, USA, may 2017. IEEE Computer Society.
  * [38] Aivin V Solatorio and Olivier Dupriez.  Realtabformer: Generating realistic relational and tabular data using transformers.  arXiv preprint arXiv:2302.02041, 2023.
  * [39] Namjoon Suh, Xiaofeng Lin, Din-Yin Hsieh, Mehrdad Honarkhah, and Guang Cheng.  Autodiff: combining auto-encoder and diffusion model for tabular data synthesizing.  In NeurIPS 2023 Workshop on Synthetic Data Generation with Generative AI, 2023.
  * [40] Lan Tao, Shirong Xu, Chi-Hua Wang, Namjoon Suh, and Guang Cheng.  Discriminative estimation of total variation distance: A fidelity auditor for generative data.  arXiv preprint arXiv:2405.15337, 2024.
  * [41] Boris van Breugel, Hao Sun, Zhaozhi Qian, and Mihaela van der Schaar.  Membership inference attacks against synthetic data through overfitting detection, 2023.
  * [42] Laurens van der Maaten and Geoffrey E. Hinton.  Visualizing data using t-sne.  Journal of Machine Learning Research, 9:2579–2605, 2008.
  * [43] Chi-Hua Wang and Guang Cheng.  Badgd: A unified data-centric framework to identify gradient descent vulnerabilities.  arXiv preprint arXiv:2405.15979, 2024.
  * [44] David S. Watson, Kristin Blesch, Jan Kapar, and Marvin N. Wright.  Adversarial random forests for density estimation and generative modeling.  In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 5357–5375. PMLR, 25–27 Apr 2023.
  * [45] Lei Xu, Maria Skoularidou, Alfredo Cuesta-Infante, and Kalyan Veeramachaneni.  Modeling tabular data using conditional gan.  In Neural Information Processing Systems, 2019.
  * [46] Andrew Yale, Saloni Dash, Ritik Dutta, Isabelle Guyon, Adrien Pavao, and Kristin P. Bennett.  Assessing privacy and quality of synthetic health data.  In Proceedings of the Conference on Artificial Intelligence for Data Discovery and Reuse, AIDR ’19, New York, NY, USA, 2019. Association for Computing Machinery.
  * [47] Jinsung Yoon, Lydia N Drumright, and Mihaela Van Der Schaar.  Anonymization through data synthesis using generative adversarial networks (ads-gan).  IEEE journal of biomedical and health informatics, 24(8):2378–2388, 2020.
  * [48] Jinsung Yoon, Lydia N Drumright, and Mihaela van der Schaar.  Anonymization through data synthesis using generative adversarial networks (ads-gan).  IEEE journal of biomedical and health informatics, 24(8):2378—2388, August 2020.
  * [49] Jinsung Yoon, James Jordon, and Mihaela van der Schaar.  PATE-GAN: Generating synthetic data with differential privacy guarantees.  In International Conference on Learning Representations, 2019.
  * [50] Hengrui Zhang, Jiani Zhang, Zhengyuan Shen, Balasubramaniam Srinivasan, Xiao Qin, Christos Faloutsos, Huzefa Rangwala, and George Karypis.  Mixed-type tabular data synthesis with score-based diffusion in latent space.  In The Twelfth International Conference on Learning Representations, 2024.
  * [51] Zilong Zhao, Aditya Kunar, Robert Birke, and Lydia Y. Chen.  Ctab-gan: Effective table data synthesizing.  In Vineeth N. Balasubramanian and Ivor Tsang, editors, Proceedings of The 13th Asian Conference on Machine Learning, volume 157 of Proceedings of Machine Learning Research, pages 97–112. PMLR, 17–19 Nov 2021.

##  Appendix A Ablation study

DPI requires a practitioner to specify a distance metric and $K$ number of
nearest neighbors in order to be deployed. This presents a hyperparameter
tuning problem as to what measure of distance should be used and how large the
neighbors should be. We replicate the experiment from Section 5.4 but this
time with common distance metrics (L1 and L2) as well as a variety of $K$
sizes (5, 10, 20, 30). We plot the means and standard deviations of the
corresponding DPI MIA attacks in Figure 7. While the success of the attacks
vary with lower sample sizes, each attack follows a clear trend with each,
eventually seeing smaller deviations at the maximum sample sizes.

Figure 7: Ablation Results for Various Distance Measures and $K$ Size Choices.

##  Appendix B Model Descriptions

In all experiments, we use the implementations of these models from the Python
package Synthcity [35]. For benchmarking purposes we use the default
hyperparameters for each model. A brief description for each model is as
follows:

CTGAN [45]: (Conditional Tabular Generative Adversarial Network) uses a GAN
framework with conditional generator and discriminator to capture multi-modal
distributions. It uses mode normalization to better learn mixed-type
distributions.

TVAE [45]: (Tabular Variational Auto-Encoder) is very similiar to CTGAN in its
use of mode normalizing techniques, but rather than using a GAN architecture,
instead employees A VAE.

Normalizing Flows (NFlow) [12]: Normalizing flows transform a simple base
distribution (e.g. Gaussian) into a more complex one matching the data by
applying a sequence of invertible, differentiable mappings.

Bayesian Network (BN) [4],: Bayesian Networks use a Directed Acyclic Graph to
represent the joint probability distribution over variables as a product of
marginal and conditional distributions. It then samples the empiric
distributions estimated from the training dataset.

Adversarial Random Forests (ARF) [44]: ARFs extend the random forest model by
adding an adversarial stage. Random forests generate synthetic samples which
are scored against the real data by a discriminator network. This score is
used to re-train the forests iteratively.

Tab-DDPM [23]: Tabular Denoising Diffusion Probabilistic Model adapts the DDPM
framework from image synthesis. It iteratively refines random noise into
synthetic data by learning the data distribution through gradients of a
classifier on partially corrupted samples with gaussian noise.

PATEGAN [49]: The PATEGAN model uses a neural encoder to map discrete tabular
data into a continuous latent representation which is sampled from during
generation by the GAN discriminator and generator pair.

Ads-GAN [47]: Ads-GAN uses a GAN architecture for tabular synthesis but also
adds an identifiability metric to increase its ability to not mimic training
data.

##  Appendix C Membership Inference Attack Descriptions

A description of each of the Membership Inference Attacks referenced in the
paper are as follows:

LOGAN [17]: LOGAN proposes a variety of MIA strategies. A black box version of
their attack involves training a Generative Adversarial Network (GAN) on the
synthetic dataset and using the discriminator to score test data. A calibrated
version improves upon this by training a binary classifier to distinguish
between the synthetic and reference dataset. In this paper we only benchmark
the calibrated version.

GAN Leaks/ GAN Leaks Calibrated [8]: GAN Leaks is a black box attack that
scores test data based on a sigmoid score of the distance to the nearest
neighbor in the synthetic dataset. GAN Leaks Calibrated improves on this with
the inclusion of a reference set in which this distance is subtracted from the
distance to the closest record in the reference set.

MC [18]: MC is based on counting the amount of observations in the synthetic
dataset that fall into the neighborhood of a test point (Monte Carlo
Integration). However, they do not consider a reference dataset and the choice
of distance for what to consider a neighborhood is a non-trivial
hyperparameter to tune.

DOMIAS [41]: DOMIAS is a calibrated attack which scores test data by
performing density estimation on the synthetic and reference datasets to then
calculate the probability ratio of the test data being from the synthetic vs
reference distributions.


#  $\sf{\mathcal{D}iCA}$: A Hardware-Software Co-Design for Differential
Check-Pointing in Intermittently Powered Devices

Antonio Joia Neto, Adam Caulfield, Chistabelle Alvares, Ivan De Oliveira Nunes
Rochester Institute of Technology
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Intermittently powered devices rely on opportunistic energy-harvesting to
function, leading to recurrent power interruptions. Therefore, check-pointing
techniques are crucial for reliable device operation. Current strategies
involve storing snapshots of the device’s state at specific intervals or upon
events. Time-based check-pointing takes check-points at regular intervals,
providing a basic level of fault tolerance. However, frequent check-point
generation can lead to excessive/unnecessary energy consumption. Event-based
check-pointing, on the other hand, captures the device’s state only upon
specific trigger events or conditions. While the latter reduces energy usage,
accurately detecting trigger events and determining optimal triggers can be
challenging. Finally, differential check-pointing selectively stores state
changes made since the last check-point, reducing storage and energy
requirements for the check-point generation. However, current differential
check-pointing strategies rely on software instrumentation, introducing
challenges related to the precise tracking of modifications in volatile memory
as well as added energy consumption (due to instrumentation overhead).

This paper introduces $\sf{\mathcal{D}iCA}$, a proposal for a
hardware/software co-design to create differential check-points in
intermittent devices. $\sf{\mathcal{D}iCA}$ leverages an affordable hardware
module that simplifies the check-pointing process, reducing the check-point
generation time and energy consumption. This hardware module continuously
monitors volatile memory, efficiently tracking modifications and determining
optimal check-point times. To minimize energy waste, the module dynamically
estimates the energy required to create and store the check-point based on
tracked memory modifications, triggering the check-pointing routine optimally
via a non-maskable interrupt. Experimental results show the cost-effectiveness
and energy efficiency of $\sf{\mathcal{D}iCA}$, enabling extended application
activity cycles in intermittently powered embedded devices.

###### Index Terms:

Intermittent Computing, Energy Harvesting, Check-pointing

##  I Introduction

In contrast to traditional devices that depend on batteries or external power
sources, energy harvesting devices capitalize on ambient energy from the
surrounding environment to fuel their operations. By leveraging opportunistic
energy sources such as solar power[19] and kinetic energy[8, 9], intermittent
computing enables energy harvesting devices to operate under unpredictable
power interruptions. By eliminating the need for batteries, these devices
become more sustainable and environmentally friendly, as they reduce
electronic waste [30]. Moreover, battery-less devices offer increased
convenience and autonomy since they do not require frequent battery
replacements or recharging. This allows for significantly reduced device size
and weight, enabling sleeker and more compact designs [18]. By removing the
need for large batteries, battery-less devices open up new possibilities for
miniaturization and integration into various applications [9].

On the other hand, power disruptions on intermittent devices present
challenges to reliable operation, including data loss, difficulties in state
preservation, task resumption, and system instability [22, 28]. As a result,
the execution of applications in intermittent devices follows cyclic patterns,
where task execution occurs during periods of power availability, followed by
power depletion. These cycles require strategies to maintain state across
power depletion cycles, ensuring correct operation.

A naive solution to this problem is the exclusive use of Non-Volatile Memory
(NVM), such as FRAM, to store all data. While a completely FRAM-based solution
ensures reliability, it increases energy consumption due to increased access
latency when compared to volatile memory, such as SRAM. Conversely, an
exclusively SRAM-based implementation offers high energy efficiency while
lacking reliability across power depletion cycles [17, 7]. An alternative
approach is to integrate check-pointing into the execution cycles of
intermittent devices. Check-pointing involves regularly saving the volatile
system state to NVM, creating snapshots that capture the current execution
context. Therefore, after power depletion, the system can restore the latest
check-point and resume execution properly.

One approach to implement the check-pointing is to modify the original
software with additional logic to determine when a minimum energy level has
been reached and save the program context to NVM [29, 11, 31]. Although
functional, these techniques also extend the program’s runtime and thus incur
additional energy costs, reducing the original application’s activity cycle.
Alternative techniques propose one-time check-pointing [7, 6] that is
triggered when the supplied voltage falls below a certain threshold. However,
the latter does not track the modifications made to the volatile memory (VM),
requiring the entire VM to be copied to NVM at each check-point. This process
also incurs a significant energy cost.

Differential check-pointing is an approach aimed at minimizing the amount of
data copied from the VM to the NVM. The fundamental concept is to track
modified memory addresses and copy only the modified memory blocks to NVM for
each check-point. This approach has led to a notable reduction in both run-
time and energy costs associated with check-pointing and has been
systematically employed in prior work [2, 4, 10]. However, prior differential
check-pointing schemes are implemented by instrumenting the application source
code, still introducing energy and run-time overhead.

Figure 1: Illustration of $\sf{\mathcal{D}iCA}$’s high level architecture

###  I-A Contributions

Given the popularity of intermittent computing applications, we argue that
future devices could be manufactured with minimal hardware support to
facilitate check-pointing and reduce associated energy and run-time costs.
With that premise in mind, we propose $\sf{\mathcal{D}iCA}$: a Differential
Check-point Assistant based on a hardware/software co-design.
$\sf{\mathcal{D}iCA}$ eliminates software instrumentation and application code
modifications and dynamically determines optimal differential check-pointing
times based on the amount of memory to be saved to NVM. More specifically,
$\sf{\mathcal{D}iCA}$ comprises:

  * •

A lightweight (and energy efficient) hardware module – called Memory
Modification Tracker – used to efficiently mark modified segments in VM. This
module enables tracking of differential memory modifications without requiring
any instrumentation or code modification, simplifying and optimizing the
check-point generation.

  * •

A new interrupt source that optimizes check-point timings and reduces energy
consumption. This approach dynamically estimates the minimal supply voltage
required to perform the check-point based on the number of segments modified
in VM. When the dynamically defined threshold is reached,
$\sf{\mathcal{D}iCA}$ hardware generates a non-maskable interrupt to initiate
the check-pointing procedure.

  * •

A software routine that interacts with the $\sf{\mathcal{D}iCA}$ hardware to
copy appropriate memory segments from VM to NVM based on the optimal
parameters configured by $\sf{\mathcal{D}iCA}$ hardware module.

The intangibility of applying hardware modifications to real devices has been
a significant obstacle for check-pointing techniques, leading to a reliance on
software instrumentation. Our approach is rooted in the premise that minimal
hardware modifications are both feasible and realistic considering the recent
popularity of and demand for energy harvesting devices. We believe that, given
their distinct purposes, these devices can benefit from simple, practical, and
inexpensive hardware modifications to enhance their performance without
requiring massive architectural overhauls.

###  I-B Scope

Battery-less and intermittent computing devices are typically implemented with
micro-controller units (MCUs) that run software at bare-metal, have low-cost,
and are energy efficient. In this work, we focus on ultra low-energy MCUs
(e.g., Atmel AVR ATMega [5], TI MSP430 [16]) which feature single-core $8$\-
or $16$-bit CPUs running at low clock frequencies (usually $1$ to $16$ Mhz).
They use between $4$ and $16$ KBytes of SRAM as VM while the rest of the
address-space is available for NVM. We implement $\sf{\mathcal{D}iCA}$
prototype atop an open-source version of TI MSP430 from openCores [15].

###  I-C Organization

This paper is structured as follows. Section II presents the high-level ideas
in $\sf{\mathcal{D}iCA}$ design. Section III delves into the details of
$\sf{\mathcal{D}iCA}$ architecture and specifies $\sf{\mathcal{D}iCA}$
hardware and software components. Section IV discusses the implementation of
$\sf{\mathcal{D}iCA}$ prototype, the experimental set-up, and presents
$\sf{\mathcal{D}iCA}$ empirical evaluation. Section V discusses related work
and Section VI concludes the paper.

##  II $\sf{\mathcal{D}iCA}$ High-Level Overview

$\sf{\mathcal{D}iCA}$ is a hardware/software co-design. It includes an
inexpensive hardware module that tracks modified VM segments. Compared to
methods that perform this tracking in software, it reduces energy consumption,
enabling more instructions belonging to the original application to be
executed per power cycle. $\sf{\mathcal{D}iCA}$ hardware also implements a new
interrupt source that triggers the check-point generation, i.e., the process
of copying modified VM segments to NVM, based on the estimated required time
and available energy. Figure 1 illustrates $\sf{\mathcal{D}iCA}$ architecture.

Figure 2: Illustration of $\sf{DTable}$ memory tracking

###  II-A $\sf{\mathcal{D}iCA}$ Hardware

$\sf{\mathcal{D}iCA}$ hardware has two sub-modules: Memory Modification
Tracker ($\sf{MMT}$) and Voltage Threshold Tracker ($\sf{VTT}$).

$\sf{MMT}$ divides the volatile memory into blocks. It detects whether these
blocks have been written to by monitoring two internal CPU signals: the write
enable bit (denoted $W_{en}$), which indicates whether the MCU is writing to
the memory, and the $D_{addr}$ signal, that defines the memory address being
written to when $W_{en}=1$. Whenever $W_{en}$ is active, $\sf{\mathcal{D}iCA}$
takes the value of $D_{addr}$ and uses it as an index to set a bit in a
register vector called (Dirty-bits Table) $\sf{DTable}$, indicating that the
block to which the address $D_{addr}$ belongs to has been modified. Figure 2
depicts $\sf{\mathcal{D}iCA}$ updating $\sf{DTable}$ as VM blocks are
modified. To track the differential changes, $\sf{\mathcal{D}iCA}$ also has a
controller that allows software to reset $\sf{DTable}$ after loading the prior
check-point.

($\sf{VTT}$) generates an interrupt signal based on how many memory segments
in VM have been modified (as detected by $\sf{MMT}$). It dynamically
calculates a threshold voltage supply value, denoted $V_{ths}$. The value of
$V_{ths}$ is determined by counting the number of modified VM memory blocks,
i.e., the number of active bits in $\sf{DTable}$, to allow sufficient time for
the check-pointing routine. When the supplied voltage falls below $V_{ths}$,
indicating an impending power depletion, a non-maskable interrupt is
triggered.

###  II-B $\sf{\mathcal{D}iCA}$ Software

$\sf{\mathcal{D}iCA}$ software component is implemented as an interrupt
service routine (ISR) associated with the $\sf{VTT}$-generated interrupt.
Based on $\sf{DTable}$, the ISR captures a snapshot of modified segments in VM
and CPU registers, and copies them to NVM. After the successful check-point
generation, the system is powered off until the energy harvesting component
recharges the power supply. When the supplied voltage reaches a full charge
threshold (denoted $V_{full}$), the MCU restarts and $\sf{\mathcal{D}iCA}$
software restores the most recent check-point, allowing the system to resume
operation from the suspended state.

##  III $\sf{\mathcal{D}iCA}$ in Details

This section details $\sf{\mathcal{D}iCA}$ design. For quick reference, Table
I summarizes the notation used in the rest of the paper.

TABLE I: Notation Summary

Notation |  Description
---|---
$\sf{DTable}$ |  Bit-vector indicating memory blocks that have been modified since the last check-point
${\sf{DTable}}_{{\sf{size}}}$ |  Size of $\sf{DTable}$ (in number of bits)
$\sf{DTable}$ [d] |  d-th bit in $\sf{DTable}$
$n_{d}$ |  Number of active bits in $\sf{DTable}$
$reset$ |  A 1-bit CPU signal that sets all the DTable bits to zero
$W_{en}$ |  A 1-bit signal that indicates if the MCU is writing to memory
$D_{addr}$ |  CPU signal containing memory address being modified by the MCU when $W_{en}=1$
$BSS$ |  Block size shift
$SP$ |  Stack Pointer
$SP_{Lim}$ |  Stack Pointer Limit: lowest memory address for data allocation in the CPU stack architecture
$\sf{NVM}$ and$\sf{VM}$ |  Non Volatile Memory and Volatile Memory
${\sf{VM}}_{{\sf{size}}}$ |  Volatile Memory size
${\sf{VM}}_{min}$,${\sf{VM}}_{max}$ |  Maximum and Minimum memory addresses of $\sf{VM}$
$SF_{mask}$ |  Stack Frame mask
${\sf{VM}}^{block}_{size}$ |  Size of a memory block
$V_{ths}$ |  Supply voltage threshold
$V_{ths}(n_{d})$ |  Function mapping $n_{d}$ to $V_{ths}$

###  III-A Memory Modification Tracker (MMT)

$\sf{MMT}$ is a hardware sub-mudule designed, in its simplest form, to monitor
the memory locations written by the CPU. Central to this component is the
$\sf{DTable}$, a peripheral that enables efficient differential check-point
generation, obviating the need for instrumentation or application-specific
code modifications.

$\sf{DTable}$ is a bit-vector where each bit maps to a memory block,
sequentially, in $\sf{VM}$. Memory blocks are of pre-defined size denoted as
${\sf{VM}}^{block}_{size}$. $\sf{DTable}$’s size is determined by the total
size of the $\sf{VM}$ (${\sf{VM}}{{\sf{size}}}$) divided by
${\sf{VM}}^{block}_{size}$. ${\sf{VM}}^{block}_{size}$ defines the granularity
of memory tracking and is a design parameter chosen at MCU manufacturing time.
To simplify the hardware implementation, we restrict
${\sf{VM}}^{block}_{size}$ to powers of 2.

$\sf{MMT}$ monitors the CPU signals $W_{en}$ and $D_{addr}$ which are used by
the CPU to write to memory. As part of the underlying CPU behavior, $W_{en}$
is set to $1$ whenever a write access to memory occurs, whereas $D_{addr}$
contains the address of the memory location being written when $W_{en}=1$.
Therefore, whenever $D_{addr}$ is within $\sf{VM}$ and $W_{en}=1$, $\sf{MMT}$
determines a $\sf{DTable}$ index ($Addr$) by shifting the relative address of
$\sf{VM}$ ($D_{addr}-{\sf{VM}}_{min}$) by $\sf{BSS}$ bits, where
${\sf{BSS}}=\log_{2}^{{\sf{VM}}^{block}_{size}}$. Then $\sf{MMT}$ sets the bit
corresponding to $Addr$ in $\sf{DTable}$ to $1$. Figure 2 illustrates
$\sf{DTable}$ functionality. The specification of $\sf{MMT}$ basic behavior is
presented in Definition 1 (see Section III-B for $\sf{MMT}$ extended version
that ignores de-allocated stack frames during check-point generation).

###### Definition 1

Memory Modification Tracker Model $i\in[1,{\sf{DTable}}_{{\sf{size}}}]$
$Addr:=(D_{addr}-{\sf{VM}}_{min})\gg BSS$
${\sf{DTable}}[i]:=\begin{cases}0&\quad\text{if}\quad reset\\\
1&\quad\text{if}\quad(i=Addr)\quad\land\\\ &\quad(D_{addr}\in{\sf{VM}})\land
W_{en}\\\ {\sf{DTable}}[i]&\quad\text{Otherwise}\\\ \end{cases}$
---

Rationale. $\sf{MMT}$ detects differential memory changes between the last
check-point and the current memory state. This feature reduces the number of
memory blocks that must be copied to NVM in the next check-point, as
unmodified data remains consistent in NVM and need not be copied. To support
this functionality, the $\sf{MMT}$ module incorporates a control bit ($reset$)
that clears $\sf{DTable}$ on each power cycle (i.e., at MCU boot). Figure 3
illustrates the differential check-pointing process across subsequent check-
points based on $\sf{DTable}$.

Figure 3: Visualization of differential check-pointing using $\sf{DTable}$

###  III-B Extending $\sf{MMT}$ to Ignore De-Allocated Stack Frames

$\sf{MMT}$ basic design only sets $\sf{DTable}$ bits to track memory
modifications. However, it does not clear $\sf{DTable}$ if a memory block is
no longer in use by the program. Since functions are called (and returned
from) multiple times in most programs, $\sf{MMT}$ basic design would check-
point function stack frames that are no longer in use. Considering nested
function calls, this check-pointing approach would unnecessarily include a
large number of memory blocks related to stack frames that are no longer in
use. To address this issue, $\sf{MMT}$ is extended to clear $\sf{DTable}$ bits
associated with stack frames of functions upon their completion.

The stack frame cleaning is depicted in Figure 4. It uses a bit mask, called
$SF_{mask}$, that masks $\sf{DTable}$ entries. This mask indicates whether the
corresponding D-table bit is no longer in use. $SF_{mask}$ values are
determined based on two values. The first, $SP_{LIM}$, defines the lowest
memory address111The use of the “lowest memory address” as the limit assumes
that the stack grows downwards in the underlying MCU architecture. that can be
used for stack allocation in the MCU. The second, $SP$, is the current stack
pointer, i.e., a CPU signal that contains the address of the top of the
currently allocated stack. Therefore, at any given time, the memory region
between $SP$ and $SP_{LIM}$ is unallocated.

To produce $SF_{mask}$, the relative memory positions of $SP$ and $SP_{LIM}$
with respect to the $\sf{VM}$ are computed by subtracting ${\sf{VM}}_{min}$
from both input parameters. ${\sf{VM}}_{min}$ indicates the lowest memory
address of $\sf{VM}$. Next, the indices that correspond to these relative
memory addresses in $\sf{DTable}$ are obtained by shifting the resulting
values by $BSS$. This generates the indices $ID_{SP}$ and $ID_{SP_{LIM}}$. The
mask is then generated by setting all indices between $ID_{SP}$ and
$ID_{SP_{LIM}}$ to 0 and leaving all others as 1. $\sf{MMT}$ behavior,
extended with the stack frame cleaner, is specified in Definition 2.

###### Definition 2

Memory Modification Tracker with Stack Frame Cleaner: • Stack Frame mask:
$i\in[1,{\sf{DTable}}_{{\sf{size}}}]$ $ID_{SP}:=((SP-{\sf{VM}}_{min})\gg BSS)$
$ID_{SP_{LIM}}:=((SP_{Lim}-{\sf{VM}}_{min})\gg BSS)$ $SF_{mask}[i]:=(i\leq
ID_{SP})\lor(i\geq ID_{SP_{LIM}})$ • $\sf{DTable}$ with Stack Frame Cleaner:
${\sf{DTable}}[i]:=\begin{cases}0&\quad\text{if}\quad SF_{mask}[i]\lor
reset\\\ 1&\quad\text{if}\quad(i=Addr)\quad\land\\\
&\quad(D_{addr}\in{\sf{VM}})\land W_{en}\\\
{\sf{DTable}}[i]&\quad\text{Otherwise}\\\ \end{cases}$
---

###  III-C Voltage Threshold Tracker

To reduce power consumption, $\sf{\mathcal{D}iCA}$ establishes the ideal
moment to start the check-pointing routine. To this end, it implements a non-
maskable interrupt source that is triggered when the system’s supplied voltage
($V_{supply}$) falls below a dynamically defined threshold ($V_{ths}$).
$V_{ths}$ serves as a proxy for the amount of energy required for the check-
pointing routine to fully execute before $V_{supply}$ drops below to a level
that is insufficient to sustain MCU operation. $V_{ths}$ is calibrated based
on the number ($n_{d}$) of active bits of in $\sf{DTable}$ (see Section III-D
for details). When $V_{ths}$ is reached, the interrupt is triggered.

$n_{d}$ default value is $0$ after loading a check-point. It is incremented by
one whenever a $\sf{DTable}$ value changes from 0 to 1 (as detected with the
operation $[\neg{\sf{DTable}}[Addr]\land W_{en}]$). Conversely, when a bit in
the $\sf{DTable}$ is cleared (due to stack frame cleaning) $n_{d}$ is
decremented. To determine the number of bits cleared due to stack frame
cleaning, $\sf{\mathcal{D}iCA}$ checks the previous stack pointer index,
denoted $ID_{SP}^{t-1}$ and subtracts it from the current index $ID_{SP}^{t}$.
If the result is greater than zero, it is subtracted from $n_{d}$. The value
of $n_{d}$ is then used to compute the $V_{ths}$, as detailed in Section
III-D. The interrupt signal generation is specified in Definition 3.

###### Definition 3

Voltage Threshold Tracker Model: • Stack Frame reduction counter:
$ID_{d}:=ID_{SP}^{t}-ID_{SP}^{t-1}$ • Dtable bit counter:
$n_{d}:=\begin{cases}0&\quad\text{if }reset\\\ n_{d}+1&\quad\text{elif
}(\neg{\sf{DTable}}[Addr]\land W_{en})\\\ n_{d}-ID_{d}&\quad\text{elif
}(ID_{d}>0)\\\ n_{d}&\quad\text{Otherwise}\end{cases}$ • Interrupt Signal:
$IT_{sig}\leftarrow V_{supply}<V_{ths}(n_{d})$
---

Figure 4: Visualization of the $\sf{DTable}$ stack frame trash cleaning

###  III-D Voltage Threshold ($V_{ths}$) Calibration

$V_{ths}$ is determined by two factors: $n_{d}$ and a constant $\lambda$. A
device calibration phase is conducted at system deployment time to determine
$\lambda$. The calibration process involves fine-tuning $\lambda$ to the
specific MCU in order to obtain an optimal $V_{ths}(n_{d})$ function for that
particular device. Similar to prior work [6], we assume that the voltage
supply decay between $3.6$V (fully charged supply) to $2.0$V (minimal
operational threshold) is linear. Therefore, $\lambda$ is determined by
measuring the total amount of blocks that can be copied in one full device
power cycle ($N$) and dividing $1.6$V by $N$.

Implementation of $V_{ths}(n_{d})$: In order to avoid hardware
multiplications, the product of $\lambda$ and $n_{d}$ is computed using
addition operations. Initially, the threshold voltage $V_{ths}$ is set to
$V_{min}$. As $n_{d}$ increases or decreases, an additional register
$n_{d}^{\prime}$ tracks the values of $n_{d}$ with a unitary increment or
decrement. This additional register is necessary because $n_{d}$ can decrease
by more than one value at a time, due to the stack frame cleaner. This is
specified in Definition 4.

###### Definition 4

$V_{ths}$ Calibration Model: $V_{ths}(0)=V_{min}$
$n_{d}^{\prime}:=\begin{cases}n_{d}^{\prime}+1&\quad\text{if}\quad
n_{d}>n_{d}^{\prime}\\\ n_{d}^{\prime}-1&\quad\text{if}\quad
n_{d}<n_{d}^{\prime}\\\ n_{d}^{\prime}&\quad\text{if}\quad
n_{d}=n_{d}^{\prime}\\\ \end{cases}$
$V_{ths}:=\begin{cases}V_{ths}+\lambda&\quad\text{if}\quad
n_{d}>n_{d}^{\prime}\\\ V_{ths}-\lambda&\quad\text{if}\quad
n_{d}<n_{d}^{\prime}\\\ V_{ths}&\quad\text{if}\quad n_{d}=n_{d}^{\prime}\\\
\end{cases}$
---

###  III-E Check-Point Generation

When the check-pointing ISR is triggered ($IT_{sig}=1$), $\sf{\mathcal{D}iCA}$
software executes to copy $\sf{VM}$ memory blocks that are marked in
$\sf{DTable}$ to a dedicated region in NVM. Enough space in $\sf{NVM}$ should
be reserved for this purpose.

Before the check-pointing process, a flag stored in the NVM is set to $True$,
indicating the active state of the check-pointing process. Once check-pointing
is completed, the flag is unset. If the check-pointing process is not
successfully completed, the value of $\lambda$ can be adjusted to a more
conservative value for the subsequent power cycle.

In order to generate the VM snapshot using the $\sf{DTable}$, the
$\sf{\mathcal{D}iCA}$ software iterates through each bit of $\sf{DTable}$. If
a bit is 0, the iteration proceeds to the next bit. If the bit is 1, the
memory block associated with that bit (of size ${\sf{VM}}^{block}_{size}$) is
copied to its corresponding position in NVM. This process is shown in
Algorithm 1.

Data: $\sf{DTable}$,${\sf{DTable}}_{{\sf{size}}}$; $\overline{{\sf{NVM}}}$ =
pointer to the first position of nonvolatile memory related to the check-
point, ${\sf{VM}}$ = pointer to the first position of the ram memory, $b$ =
${\sf{VM}}^{block}_{size}$

for  _$i\leftarrow 0$ to ${\sf{DTable}}_{{\sf{size}}}-1$_ do

if  _${\sf{DTable}}[i]$ is 1_ then

memcpy($\overline{{\sf{NVM}}}[b*i]$, ${\sf{VM}}[b*i]$, $b$);

end if

end for

Algorithm 1 Memory check-pointing using $\sf{DTable}$

###  III-F Execution Resumption

When resuming execution in a new power cycle, $V_{ths}$ can be re-calibrated
by adjusting $\lambda$. The system must also check the integrity of the
current check-point. If no check-point is found or if it is corrupted (or
incomplete), the application starts anew. If a valid check-point exists, it
must be reloaded by copying the check-point data from NVM to the VM, and
restoring the CPU registers. Additionally, after copying the check-point data
to NVM, $\sf{DTable}$ and $n_{d}$ are cleared. This step sets
$\sf{\mathcal{D}iCA}$ up for check-pointing the next power cycle. Finally, the
Program Counter (PC) is loaded with the address that was meant to be executed
by the application in the previous power cycle immediately before
$\sf{\mathcal{D}iCA}$ interrupt was triggered.

##  IV Prototype & Experiments

We synthesize $\sf{\mathcal{D}iCA}$ using a Xilinx Artix-7 FPGA [33], on a
Basys-3 [13] prototyping board. The Xilinx Vivado tool-set [32] was used for
synthesizing the on top of the openMSP430 [15] MCU core. $\sf{\mathcal{D}iCA}$
was written in the Verilog hardware description language. Each module
implements the logic outlined in Section III. $\sf{\mathcal{D}iCA}$ was
implemented in 368 lines of Verilog code for the MMT and VTT hardware modules
(including their integration with the underlying openMSP430 core) and 201
lines of C code for $\sf{\mathcal{D}iCA}$ software ISR and check-point
recover.

In addition to the FPGA-based prototype, we perform complementary experiments
using a low-energy device for realistic energy results. We use the
MSP430FR2476 MCU for these experiments, featuring 8kB of SRAM (VM) and 64KB of
FRAM (NVM) and running at a CPU clock frequency of 1MHz.

###  IV-A Profiling ${\sf{VM}}^{block}_{size}$

An important manufacturing time decision is to determine
${\sf{VM}}^{block}_{size}$ in $\sf{\mathcal{D}iCA}$. This decision has a
direct impact on the number of bits in $\sf{DTable}$, thereby affecting the
hardware size. However, it also plays a vital role in enhancing the
granularity of memory-tracking, which has the potential to reduce check-
pointing time and energy consumption. To determine the optimal value of
${\sf{VM}}^{block}_{size}$, we profile the check-pointing run-time against
various values. The results for ${\sf{VM}}^{block}_{size}$ varying from 8 to
512 Bytes are presented in the Figure 5.

Figure 5: Profiling of copy run-time vs. ${\sf{VM}}^{block}_{size}$

The results show that smaller ${\sf{VM}}^{block}_{size}$ incur longer run-
times for copying the same amount of memory, even for small memory amounts.
This can be attributed to the inherent overhead associated with the copy
operation, encompassing memory address calculations, data transfers, and
synchronization. Moreover, smaller ${\sf{VM}}^{block}_{size}$ result in larger
$\sf{DTable}$ sizes, necessitating a more extensive search to identify
modified bits, which further contributes to the augmented check-pointing run-
time. Conversely, as the ${\sf{VM}}^{block}_{size}$ increases, it becomes
apparent that larger values are constrained by a minimum overhead, which
increases proportionally due to the granularity of memory-tracking.

Based on these experiments, we determined that the optimal
${\sf{VM}}^{block}_{size}$ for the MSP430FR2476 is $128$ Bytes, as it provides
the most favorable balance between run-time and granularity. When selecting
such parameters, it is crucial to take into account the characteristics of the
device’s memory and its clock frequency. These factors can vary across
different devices and significantly influence the profile. Consequently, it is
important to highlight that our prototype’s profile may not be optimal to
other devices or MCU models. That being said, we use $128$-Byte blocks as the
reference value for the remainder of the experiments in $\sf{\mathcal{D}iCA}$
evaluation.

###  IV-B Hardware Footprint Overhead

We assess the hardware cost in terms of additional Look-up Tables (LUTs) and
flip-flops/registers (FFs). The increase in LUTs reflects the additional chip
cost/size attributed to combinatorial logic. The increase in FFs indicates the
additional state required by sequential logic. Figure 6 shows the hardware
cost of unmodified openMSP430 and the additional cost of $\sf{\mathcal{D}iCA}$
hardware when configured to monitor memory blocks from 16 to 512 Bytes.

Figure 6: Hardware cost of unmodified openMSP430 compared to additional cost
of $\sf{\mathcal{D}iCA}$ with ${\sf{VM}}^{block}_{size}$ of 16 to 512 Bytes

The cost of $\sf{\mathcal{D}iCA}$ hardware is maximized when
${\sf{VM}}^{block}_{size}$ is at the lowest value of 16-Bytes. With this
configuration, $\sf{\mathcal{D}iCA}$ hardware incurs the maximum overhead with
additional 730 LUTs and 561 FFs. However, this additional cost decreases as
${\sf{VM}}^{block}_{size}$ increases. For instance, configuring
$\sf{\mathcal{D}iCA}$ hardware to monitor 512-Byte blocks only requires 49
LUTs and 58 FFs. For a 128-Byte configuration, which we determined has an
ideal check-pointing runtime (see Section IV-A), additional 114 LUTs and 106
FFs are required. Configuring $\sf{\mathcal{D}iCA}$ hardware to monitor
128-Byte blocks causes an increase of $\approx 8.7$% relative to the
unmodified openMSP430 core.

###  IV-C Hardware Energy Overhead

While the added hardware modules eliminate the need for software-based memory
tracking (and associated energy consumption), they also drain energy at
runtime. We use Vivado synthesis tool to estimate $\sf{\mathcal{D}iCA}$’s
power consumption on the Basys3 FPGA board. In this analysis, we consider
$\sf{\mathcal{D}iCA}$ configured for 128-Byte memory blocks. The MCU,
including openMSP430 default set of peripherals and $\sf{\mathcal{D}iCA}$,
consumes 89 mW of static power whereas $\sf{\mathcal{D}iCA}$ hardware alone is
reported222Vivado does not report energy consumption units under 1mW, treating
such small values as negligible. Thus, 1mW is the upper bound for
$\sf{\mathcal{D}iCA}$ consumption because it is not possible to obtain precise
measures below this value. In reality, however, $\sf{\mathcal{D}iCA}$ may
consume significantly less than $1$ mW. to draw less than $1$ mW. Therefore,
$\sf{\mathcal{D}iCA}$ is responsible for less than $1.1$%, of the device’s
static power consumption.

The dynamic power drawn depends on the frequency of memory writes performed by
the software. We consider an application that writes to all memory blocks in a
loop to evaluate the worst case. In this scenario, the unmodified openMSP430
(along with peripherals) draws 234 mW of dynamic power. When equipped with
$\sf{\mathcal{D}iCA}$, the dynamic power increases to 241 mW, representing a
$\mathcal{\approx}$ 2.9% increase.

We note that these estimates are based on the FPGA deployment and may vary
once the MCU design is manufactured as an integrated circuit.

Figure 7: Number of power cycles required to compute five application test-
cases: $\sf{\mathcal{D}iCA}$ vs. two related check-pointing methods

###  IV-D Power Cycle Efficiency

To evaluate the efficacy of $\sf{\mathcal{D}iCA}$, we compare its performance
with prior related work with respect to the amount of power cycles required to
complete five distinct computations. Our benchmark considers five well-known
algorithms: an AES encryption block cypher, a matrix multiplication, a SHA256
cryptographic hash function, a bit counting function, and a Depth-First Search
(DFS) algorithm. To gauge how well our approach performs in comparison to
other methods that trigger the check-point based on Voltage thresholds, we
implemented an optimized version of Hibernus++ [6] (see related work in
Section V). Our implementation of Hibernus++ triggers the check-point within
the time required to copy VM (8 kB) before energy depletes. Furthermore, to
compare our method with existing differential check-pointing approaches, we
integrated a software instrumentation version of a memory modification monitor
into Hibernus++, drawing upon prior work [3] as a reference.

In our experiment, we set up four distinct experimental configurations, each
considering an MCU equipped with a capacitors of different capacitance, used
to store harvested energy. By varying the capacitance values, our objective is
to examine the influence of varying power supply decays on the performance of
$\sf{\mathcal{D}iCA}$. The results are presented in Figure 7.

Across the four experimental capacitance configurations, we observed that
$\sf{\mathcal{D}iCA}$ consistently outperforms Hibernus++. It also outperforms
the instrumentation-based differential check-pointing in most cases, requiring
fewer execution cycles to run the bench-marked algorithms. The impact of this
outcome becomes more pronounced in setups characterized by lower capacitance,
where the rate of power supply decays is elevated. This occurs because, with
more power cycles, the check-pointing routine tends to occupy a more
substantial portion of the MCU execution time. As a result, the difference
prior methods and $\sf{\mathcal{D}iCA}$ is more pronounced.

It’s important to note that $\sf{\mathcal{D}iCA}$ and other techniques from
the literature are not mutually exclusive. $\sf{\mathcal{D}iCA}$ is compatible
and interoperable with a diverse array of existing strategies, allowing for a
potential combination of approaches to further enhance the efficiency and
effectiveness of inttermittent applications.

##  V Related Work

###  V-A Traditional Check-Pointing

Differential (a.k.a. incremental) check-pointing [23, 27, 26, 1, 21] is widely
studied for traditional computing systems. These systems are developed to
operate on high-end devices and thus prioritize performance. Since they do not
consider devices that operate on intermittent power supplies or have limited
computational/storage resources, these techniques rely on tasks that low-end
MCUs are not capable of performing, such as maintaining complex data
structures [20, 1], or relatively expensive hardware support [14, 25, 26] to
compute the differentials and store the check-point. Check-points in these
systems also have different purposes, e.g., fault tolerance, load-balancing,
and data concurrency across parallel servers.

###  V-B Check-Pointing in Intermittently Powered Devices

Energy-efficient check-pointing schemes are required for intermittently
powered devices that harvest their own supply of energy. Compile-time
techniques [29, 11] instrument the application source code with additional
function calls that check the device’s current power. They are placed at
specific points in the program’s control flow, such as each backward edge of a
loop or function returns. To properly create a check-point, the program
context must be written in NVM, including all registers and data currently in
use. Therefore frequent check-pointing can result in additional energy losses.

To reduce the overhead, runtime techniques [7, 6] determine the proper time
for a check-point to be made while the device operates. The time to create a
check-point is determined by employing a hardware-based interrupt to check the
voltage supply periodically, and a check-pointing routine is executed once the
voltage reaches a minimum threshold, reducing the number of check-points. In
contrast with $\sf{\mathcal{D}iCA}$, prior runtime techniques save all
registers and the entire VM at each check-point.

An alternative approach to further reduce the size of check-points is to save
just the changes in a similar manner to differential check-points in
traditional computing. However, computing the differentials in an energy-
efficient and low-cost manner for intermittent computing devices is
challenging. Some techniques use software to iterate over all addresses of VM
[10] and compare them to the prior check-point. Others compare the hashes of
memory blocks [4]. DICE [3] computes the differentials by maintaining an
internal modification record, and the application software is instrumented
with function calls that records differentials. DINO [22] extends C’s
programming model by providing compiler-aided analysis to place task-
boundaries, where check-points and data versioning takes place. As an
alternative, new programming abstractions that operate on data in NVM at all
times have been proposed. For instance, Chain [12] proposes a new program
abstraction that guarantees that the state of self-contained tasks is
preserved in NVM. Unlike $\sf{\mathcal{D}iCA}$, these techniques either depend
on additional software, software modification via instrumentation, or new
programming abstractions.

##  VI Conclusion

We proposed $\sf{\mathcal{D}iCA}$, a lightweight hardware/software co-design
to support efficient differential check-pointing for intermittently powered
devices. $\sf{\mathcal{D}iCA}$ eliminates the need for application code
modifications or instrumentation, simplifying and optimizing check-point
generation. In addition, it implements a non-maskable interrupt to dynamically
estimate optimal check-pointing times, thereby increasing the active period of
applications during a power cycle. $\sf{\mathcal{D}iCA}$ interrupt triggers a
software routine that complements the hardware, efficiently copying modified
memory segments from volatile to non-volatile memory. We implemented and
evaluated $\sf{\mathcal{D}iCA}$ with an FPGA deployment. $\sf{\mathcal{D}iCA}$
open-source prototype is available at [24].

## Acknowledgements

We thank the ICCAD anonymous reviewers for their constructive comments and
feedback. This work was supported by the National Science Foundation (Award
#2245531) as well as a Meta Research Award (2022 Towards Trustworthy Products
in AR, VR, and Smart Devices RFP).

## References

  * [1] S. Agarwal, R. Garg, M. S. Gupta, and J. E. Moreira, “Adaptive incremental checkpointing for massively parallel systems,” in _Proceedings of the 18th annual international conference on Supercomputing_ , 2004, pp. 277–286.
  * [2] S. Ahmed, N. A. Bhatti, M. H. Alizai, J. H. Siddiqui, and L. Mottola, “Efficient intermittent computing with differential checkpointing,” in _Proceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems_ , 2019, pp. 70–81.
  * [3] ——, “Efficient intermittent computing with differential checkpointing,” in _Proceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems_ , 2019, pp. 70–81.
  * [4] F. A. Aouda, K. Marquet, and G. Salagnac, “Incremental checkpointing of program state to nvram for transiently-powered systems,” in _2014 9th International Symposium on Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC)_. IEEE, 2014, pp. 1–4.
  * [5] Atmel, “8-bit atmel microcontroller with 16/32/64/128k bytes in-system programmable flash,” Jan 2015.
  * [6] D. Balsamo, A. S. Weddell, A. Das, A. R. Arreola, D. Brunelli, B. M. Al-Hashimi, G. V. Merrett, and L. Benini, “Hibernus++: A Self-calibrating and Adaptive System for Transiently-powered Embedded Devices,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 35, no. 12, pp. 1968–1980, 2016.
  * [7] D. Balsamo, A. S. Weddell, G. V. Merrett, B. M. Al-Hashimi, D. Brunelli, and L. Benini, “Hibernus: Sustaining computation during intermittent supply for energy-harvesting systems,” _IEEE Embedded Systems Letters_ , vol. 7, no. 1, pp. 15–18, 2014.
  * [8] S. P. Beeby, M. J. Tudor, and N. White, “Energy harvesting vibration sources for microsystems applications,” _Measurement science and technology_ , vol. 17, no. 12, p. R175, 2006.
  * [9] S. Beeby and D. Zhu, “Vibration energy harvesting: fabrication, miniaturisation and applications,” _Smart Sensors, Actuators, and MEMS VII; and Cyber Physical Systems_ , vol. 9517, p. 951703, 2015.
  * [10] N. Bhatti, L. Mottola _et al._ , “Efficient state retention for transiently-powered embedded sensing,” in _Proceedings of the 2016 International Conference on Embedded Wireless Systems and Networks_ , 2016, pp. 137–148.
  * [11] N. A. Bhatti and L. Mottola, “Harvos: Efficient code instrumentation for transiently-powered embedded sensing,” in _Proceedings of the 16th ACM/IEEE International Conference on Information Processing in Sensor Networks_ , 2017, pp. 209–219.
  * [12] A. Colin and B. Lucia, “Chain: tasks and channels for reliable intermittent programs,” in _Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications_ , 2016, pp. 514–530.
  * [13] Digilent, “Basys 3 artix-7 FPGA trainer board: Recommended for introductory users,” 2018. [Online]. Available: https://store.digilentinc.com/basys-3-artix-7-fpga-trainer-board-recommended-for-introductory-users/
  * [14] B. Egger, Y. Cho, C. Jo, E. Park, and J. Lee, “Efficient checkpointing of live virtual machines,” _IEEE Transactions on Computers_ , vol. 65, no. 10, pp. 3041–3054, 2016.
  * [15] O. Girard, “openMSP430,” 2009.
  * [16] T. Instruments. Msp430 ultra-low-power sensing & measurement mcus. http://www.ti.com/microcontrollers/msp430-ultra-low-power-mcus/overview.html.
  * [17] H. Jayakumar, A. Raha, and V. Raghunathan, “Energy-Aware Memory Mapping for Hybrid FRAM-SRAM MCUs in IoT Edge Devices,” in _2016 29th International Conference on VLSI Design and 2016 15th International Conference on Embedded Systems (VLSID)_ , 2016, pp. 264–269.
  * [18] T. J. Kazmierski and S. Beeby, “Energy harvesting systems,” _Principles, Modeling and Applications; Springer Science+ Business Media LLC: New York, NY, USA_ , 2011.
  * [19] A. Khaligh and O. C. Onar, _Energy harvesting: solar, wind, and ocean energy conversion systems_. CRC press, 2017\.
  * [20] W. Kim, C. Park, D. Kim, H. Park, Y.-r. Choi, A. Sussman, and B. Nam, “{$ListDB$}: Union of $\\{$Write-Ahead$\\}$ logs and persistent $\\{$SkipLists$\\}$ for incremental checkpointing on persistent memory,” in _16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22)_ , 2022, pp. 161–177.
  * [21] R. Koo and S. Toueg, “Checkpointing and rollback-recovery for distributed systems,” _IEEE Transactions on software Engineering_ , no. 1, pp. 23–31, 1987.
  * [22] B. Lucia and B. Ransford, “A simpler, safer programming and execution model for intermittent systems,” _ACM SIGPLAN Notices_ , vol. 50, no. 6, pp. 575–585, 2015.
  * [23] S. Narayanasamy, G. Pokam, and B. Calder, “Bugnet: Continuously recording program execution for deterministic replay debugging,” in _32nd International Symposium on Computer Architecture (ISCA’05)_. IEEE, 2005, pp. 284–295.
  * [24] A. J. Neto, A. Caulfield, and I. De Oliveira Nunes, “Dica open source prototype,” https://github.com/RIT-CHAOS-SEC/DiCA.
  * [25] E. Park, B. Egger, and J. Lee, “Fast and space-efficient virtual machine checkpointing,” _ACM SIGPLAN Notices_ , vol. 46, no. 7, pp. 75–86, 2011\.
  * [26] J. S. Plank, M. Beck, G. Kingsley, and K. Li, _Libckpt: Transparent checkpointing under unix_. Computer Science Department, 1994.
  * [27] B. Randell, P. Lee, and P. C. Treleaven, “Reliability issues in computing system design,” _ACM Computing Surveys (CSUR)_ , vol. 10, no. 2, pp. 123–165, 1978.
  * [28] B. Ransford and B. Lucia, “Nonvolatile memory is a broken time machine,” in _Proceedings of the workshop on Memory Systems Performance and Correctness_ , 2014, pp. 1–3.
  * [29] B. Ransford, J. Sorber, and K. Fu, “Mementos: System support for long-running computation on rfid-scale devices,” in _Proceedings of the sixteenth international conference on Architectural support for programming languages and operating systems_ , 2011, pp. 159–170.
  * [30] Y. K. Tan, _Sustainable energy harvesting technologies: Past, present and future_. BoD–Books on Demand, 2011.
  * [31] J. Van Der Woude and M. Hicks, “Intermittent computation without hardware support or programmer intervention.” in _OSDI_ , 2016, pp. 17–32.
  * [32] Xilinx, “Vivado design suite user guide,” 2017.
  * [33] Xilinx Inc., “Artix-7 FPGA family,” 2018. [Online]. Available: https://www.xilinx.com/products/silicon-devices/fpga/artix-7.html