11institutetext: Inria, Lyon Center, France
11email<EMAIL_ADDRESS>22institutetext: Carnegie Mellon University,
United States
22email<EMAIL_ADDRESS>33institutetext: University of Waikato, New
Zealand
44institutetext: LTCI, Telecom Paris, Institut Polytechnique de Paris, France
44email<EMAIL_ADDRESS>
# Incremental Mining of Frequent Serial Episodes Considering Multiple
Occurrence

Thomas Guyet 11 Wenbin Zhang 22 Albert Bifet 3344

###### Abstract

The need to analyze information from streams arises in a variety of
applications. One of the fundamental research directions is to mine sequential
patterns over data streams. Current studies mine series of items based on the
existence of the pattern in transactions but pay no attention to the series of
itemsets and their multiple occurrences. The pattern over a window of itemsets
stream and their multiple occurrences, however, provides additional capability
to recognize the essential characteristics of the patterns and the inter-
relationships among them that are unidentifiable by the existing items and
existence based studies. In this paper, we study such a new sequential pattern
mining problem and propose a corresponding efficient sequential miner with
novel strategies to prune search space efficiently. Experiments on both real
and synthetic data show the utility of our approach.

###### Keywords:

event sequence, serial episode, multiple occurrences

##  1 Introduction

Online mining of frequent patterns over a sliding window is one of the most
important tasks in data stream mining with broad applications. In this case,
the data stream is made of items or itemsets that arrive continuously. The aim
is then to obtain a set of evolving frequent patterns over a sliding window,
in which the most recent frequent patterns as well as their evolution are
available at any time for information extraction. This motivates work on
mining frequent patterns over series of items based on their existences in the
stream [2, 17]. In this paper, to gain additional information from the stream,
we take one step further to extract frequent sequential patterns over a stream
of itemsets but also to consider their multiple occurrence in the stream.

Mining frequent sequential patterns from a single long sequence $S$ is better
known as serial episode mining [11]. Under this setting, the support of a
pattern is the number of times it occurs in $S$. The way to enumerate the
multiple occurrences of a pattern turns out to be important to have the
antimonotonicity of the measure. Among the possible enumeration strategies
[1], the minimal occurrences is the most common [11] with the seminal work
proposed in [6]. With this property, the classical breadth-first search (like
PrefixSpan [13]) or depth-first search algorithms (like GSP [14]) can be
adapted to efficiently extract the complete set of frequent sequential
patterns occurring in a static sequence. However, applying such algorithms to
maintain the recent frequent patterns over the stream would be untractable. In
addition, start from scratch each time a new item arrives in the stream is
needed, but the computation cost, in practice, is unaffordable.

To address the aforementioned challenges, this paper introduces IncSeq
111IncSeq stands for “Incremental Sequence”., a novel framework to efficiently
extract frequent serial episodes over the stream of itemsets. To the best of
our knowledge, this is the first work capable of mining series of itemsets
incrementally without the need to start from scratch. To summarize, we present
the following contributions:

  * •

The formalization of a new incremental sequential pattern mining problem,
which counts the exact number of occurrences of sequential patterns.

  * •

A complete algorithm for incremental sequential pattern mining with efficient
search space pruning.

  * •

Extensive experiments on both real and synthetic datasets.

##  2 Basic concepts and problem statement

Suppose that we have a set of items denoted $\mathcal{E}$ and $<$ defines the
total order on this set (_e.g._ lexicographic order). An itemset
$\beta=(b^{i})_{i\in[m]}\subset\mathcal{E}$ is a sub-itemset of
$\alpha=(a^{i})_{i\in[n]}\subset\mathcal{E}$, denoted
$\beta\sqsubseteq\alpha$, iff there exists a sequence of integers $1\leq
i_{1}<i_{2}<\cdots<i_{m}\leq n$ such that $\forall
k\in[m],b^{k}=a^{i_{k}}$.222$[n]$ denotes the set of the $n$ first integers
$\\{1,\dots,n\\}$. A _sequence_ $S$ is a finite ordered series of itemsets
$S=\langle s_{1},s_{2},\dots,s_{n}\rangle$. A _serial episode_ (so-called
_sequential pattern_ or pattern for short) is a _sequence_. The length of a
sequential pattern $S$, denoted $|S|$, is its the number of itemsets. The
total number of items in a pattern $S$ is denoted $\|S\|$. $T=\langle
t_{1},t_{2},\dots,t_{m}\rangle$ is a _sub-sequence_ of $S=\langle
s_{1},s_{2},\dots,s_{n}\rangle$, denoted $T\preceq S$, iff there exists a
sequence of integers $1\leq i_{1}<i_{2}<\cdots<i_{m}\leq n$ such that
$t_{k}\sqsubseteq s_{i_{k}}$ for all $k\in[m]$.

The minimal occurrences [11] of a sequential pattern $S=\langle
s_{1},\ldots,s_{n}\rangle$ in a sequence $W=\langle
w_{1},\ldots,w_{m}\rangle$, denoted $\mathcal{I}_{W}(S)$, is the list of
$n$-tuple of positions (within $W$):

$\begin{array}[]{lll}\mathcal{I}_{W}(S)=\left\\{(i_{j})_{j\in[n]}\in[m]\;|\right.&\forall
j\in[n],s_{j}\sqsubseteq w_{i_{j}},&\text{(a)}\\\ &\forall
j\in[n-1],\;i_{j}<i_{j+1},&\text{(b)}\\\
&\left(w_{j}\right)_{j\in\left[i_{1}+1,i_{n}\right]}\npreceq S,&\text{(c)}\\\
&\left(w_{j}\right)_{j\in\left[i_{1},i_{n}-1\right]}\npreceq
S\left.\right\\}&\text{(d)}\end{array}$ (1)

In Equation 1, condition $(a)$ requires that any itemset of $S$ is a sub-
itemset of an itemset of $W$, while condition $(b)$ specifies the order of
itemsets of $W$ needs to respect. In addition, any itemset of $W$ cannot be a
super-itemset of two distinct itemsets of $S$. This condition does not impose
any time constraint between itemsets. Conditions $(c)$ and $(d)$ specify
minimal occurrences: if a minimal occurrence of $S$ has been identified in the
interval $\left[i_{1},i_{n}\right]$, there can not be any minimal occurrence
of $S$ in a strict subinterval of $\left[i_{1},i_{n}\right]$. Without loss of
generality, “occurrence” denotes “minimal occurrence” in the remainder of this
paper.

Then, the _support_ of a sequential pattern $S$ in sequence $W$, denoted
$supp_{W}(S)$, is the cardinality of $\mathcal{I}_{W}(S)$, _i.e._
$supp_{W}(S)=card\left(\mathcal{I}_{W}\left(S\right)\right)$. The support
measure $supp_{W}(\cdotp)$ is anti-monotonic on the set of sequential patterns
with associated partial order $\prec$ [15]. Given a threshold $\sigma$, we say
that a sequential pattern $S$ is _frequent_ in a stream window $W$ iff
$supp_{W}(S)\geq\sigma$.

Mining frequent sequential patterns incrementally is therefore to extract
frequent sequential patterns in a sequence $W=\langle
w_{1},\ldots,w_{m}\rangle$ from the ones in $W^{\prime}=\langle
w_{0},\ldots,w_{m-1}\rangle$. This recursively mining frequent sequential
patterns enables to mine a stream of itemsets, _i.e._ to maintain the set of
frequent sequential patterns in a window sliding over a stream of itemsets.

##  3 Incremental algorithm for sequential patterns

Our proposed approach relies on representing the set of frequent sequential
patterns (or patterns for short) in a tree structure inspired by the prefixing
method of PSP [12]. PSP represents a set of frequent sequenial patterns as a
tree with two types of edges: the edges representing sequentiality
($\mathcal{S}$) between itemsets and the edges representing the composition
($\mathcal{C}$) of itemsets. Masseglia et _al._ [12] showed that such
representation is memory efficient.

Formally, a tree node $N$ is a 4-tuple
$\langle\alpha,\mathcal{I},\mathcal{S},\mathcal{C}\rangle$ where:

  * •

$\alpha=\left(a_{i}\right)_{i\in[n]}$ is a sequential pattern of size $n$,

  * •

$\mathcal{I}=\mathcal{I}_{W}(\alpha)$, the list of minimal occurrences of
$\alpha$ in $W$,

  * •

$\mathcal{S}$ is the set of descendant nodes which represent patterns
$\beta=\left(b_{i}\right)_{i\in[n+1]}$ of size $\|\alpha\|+1$ such that
$\forall i\in[n],\;a_{i}=b_{i}$,

  * •

$\mathcal{C}$ is the set of descendant nodes which represent patterns
$\beta=\left(b_{i}\right)_{i\in[n]}$ of size $\|\alpha\|+1$ such that $\forall
i\in[n-1],\;a_{i}=b_{i}$, $a_{n}\sqsubseteq b_{n}$ and $\forall
j<|a_{n}|,\;a_{n}^{j}<b_{n}^{|a_{n}|+1}$, (_i.e._ itemset $b_{n}$ extends
itemset $a_{n}$ with the item $b_{n}^{|a_{n}|+1}$).

A tree of frequent patterns, denoted $\mathcal{A}_{\sigma}(W)$, represents all
patterns of $W$ having a support greater than $\sigma$. The root node of a
prefix tree is a node of the form
$\langle\\{\\},\emptyset,\mathcal{S},\mathcal{C}\rangle$.

Let $N$ be a node of $\mathcal{A}_{\sigma}(W)$. The subtree rooted at node $N$
represents the tree composed of all descendants of $N$ (including $N$). Owing
to the anti-monotonicity property, we know that if a node has a support
greater than or equal to $\sigma$ then all its ancestors are frequent
sequential patterns in $W$. In addition, each node – apart from the root – has
a single parent. This ensures that a recursive processing of a PSP tree is
complete and non-redundant. Figure 1 exemplifies the frequent PSP tree
representation followed by its corresponding illustration.

Figure 1: Example of a tree of frequent sequential patterns ($\sigma=2$)

###### Example 1

Let $W=\langle a(bc)(abc)cb\rangle$ and $\sigma=2$. Figure 1 shows the tree
$\mathcal{A}_{\sigma}(W)$. Solid lines indicate membership in the set
$\mathcal{S}$ (Succession in the sequential pattern), while the dotted lines
indicate membership in the set $\mathcal{C}$ (Composition with the last
itemset). The node $(bc)b$, highlighted in gray, has the pattern node $(bc)$
as parent, since $(bc)b$ is obtained by concatenating $b$ to $(bc)$. The
parent node of $(bc)$ is $(b)$ and is obtained by itemset composition (dotted
line). At each node of Figure 1, the list of minimal occurrences is displayed
in the index. For example, the pattern $(bc)c$ has two occurrences:
$\mathcal{I}(\langle(bc)c\rangle)=\\{(2,3),\;(3,5)\\}$.

###  3.1 Illustration of the method

The incremental process aims at updating the tree of frequent patterns with
respect to the most recent window of the stream and determining whether the
patterns are frequent. The arrival of a new itemset in the stream triggers two
steps: (1) the deletion of occurrences related to the first itemset in the
window; (2) the addition of patterns and occurrences related to the new
incoming itemset. The addition step incurs the majority of computational load
involving three substeps: (i) merging sub-itemsets of the new itemset into the
current tree, (ii) completing the lists of occurrences, and (iii) pruning
nodes of non-frequent patterns. Our approach therefore performs the deletion
step prior to the addition of a new itemset in order to reduce the size of the
tree before the computational expensive merging and completion substeps.

Let us consider the window $W=\langle(abc)(ab)(ab)c\rangle$ of length 4, at
position 1 of the stream. Assume that $\mathcal{A}_{2}(W)$, _i.e._ the tree of
patterns with support greater than 2, has already been built. The following
steps transform the tree of frequent patterns $\mathcal{A}_{2}(W)$ into the
tree $\mathcal{A}_{2}(W^{\prime})$ upon the arrival of the new itemset $(bc)$.
These steps are illustrated in Figure 2 and detailed in the following.

Figure 2: Successive steps for updating the tree of frequent patterns upon the
arrival of itemset $(bc)$ in the window $W=\langle(abc)(ab)(ab)c\rangle$.

1\. Deletion of the first itemset: all occurrences starting at the first
(oldest) position of the window (orange occurrences at position 1 in the
example) are deleted. Then, patterns having a number of occurrences lower than
$\sigma=2$ are deleted from the tree. The result is the tree
$\mathcal{A}_{2}(\langle(ab)(ab)c\rangle)$ where $a$, $(ab)$, $b$ are
frequent. Quasi-frequent patterns (marked with asterisk in the example) are
not frequent but may become frequent as they have a support equals to
$\sigma-1$ and they are ended by an item present in the new itemset, _i.e._
$(bc)$. Such nodes are kept in the frequent tree with their occurrences as the
following completion step (see below) is not necessary for them.

2\. Merging the new current itemset $(bc)$ with every node of the tree of
patterns: this step generates all the new candidate patterns of the new
window. Intuitively, a pattern is a new candidate (_i.e._ potentially
frequent) only if it is the concatenation of a sub-itemset of $(bc)$ to a
frequent pattern of $\langle(ab)(ab)c\rangle$. In the tree representation of
frequent patterns, this concatenation can be seen as extending each node of
$\mathcal{A}_{2}(\langle(ab)(ab)c\rangle)$ with the itemset tree
$\mathcal{T}_{(bc)}$ representing all sub-itemsets of $(bc)$.

In Figure 2, the tree $\mathcal{T}_{(bc)}$ is merged with the four non-quasi-
frequent nodes of $\mathcal{A}_{2}(\langle(ab)(ab)c\rangle)$:

  * •

with the root node (green occurrences): all subsequences of $(bc)$ become
potentially frequent.

  * •

with the nodes $a$, $(ab)$, $b$ (blue occurrences): all patterns starting with
one of these three patterns (frequent in $\langle(ab)(ab)c\rangle$) and
followed by a sub-itemset of $(bc)$ become potentially frequent.

We term “tree merging” because if a node already exists in the tree (_e.g._
node $(b)$), the occurrences related to the new itemset are added to the list
of existing occurrences. The list of occurrences of $(b)$ becomes
$\\{(2),(3),(5)\\}$. We know that each of these nodes holds all the
occurrences of the associated pattern in $W^{\prime}$. New nodes are noted in
bold face in the frequent tree after the merging step in Figure 2. Each of
these new nodes of $\mathcal{A}^{f}$, _e.g._ the node $(bc)$, has an
occurrence list consisting of only one occurrence of a sub-itemset of $(bc)$.
Quasi-frequent nodes (nodes marked with the asterisk) are not merged with the
itemset tree $\mathcal{T}_{(bc)}$. Their occurrence lists are simply updated
when needed.

3\. Completion of occurrences’ lists: Exclusively for new candidate nodes, it
is necessary to scan the window $W^{\prime}$ once again to build the complete
list of occurrences of a pattern. For example, the node $ab$ is associated
with the list $\\{(3,5)\\}$. This list must be completed with the occurrences
of $ab$ in the previous window ($\\{(2,3)\\}$). As $\langle ab\rangle$ was
unfrequent in $W$, we must retrieve their occurrences. Red occurrences of the
tree $\mathcal{A}^{c}$ in Figure 2 show the occurrences added by completion.

4\. Pruning non-frequent patterns: $\mathcal{A}^{c}$, the tree obtained after
completion, contains new candidate patterns with complete lists of
occurrences. The last step removes patterns with an occurrences’ list of size
strictly lower than $\sigma=2$ yielding the tree
$\mathcal{A}_{2}(W^{\prime})$.

###  3.2 Merging a tree of an itemset into a tree of frequent patterns

Now, we detail the merging step which integrates the itemset tree
$\mathcal{T}$ into the pattern tree $\mathcal{A}$. Then, we explain the
completion of occurrences.

Algorithm 1 describes how the itemset tree $\mathcal{T}$ is merged with every
node of the frequent patterns tree $\mathcal{A}$. It consists of two main
steps:

  * •

prefixing the itemset tree $\mathcal{T}$ with the pattern of node $N$,

  * •

recursively merging the prefixed $\mathcal{T}$ with descendants of node $N$
(_cf._ Algorithm 2).

Algorithm 1 Merging: merging the itemset tree $\mathcal{T}$ with every node of
the tree of patterns $\mathcal{A}$.

1:function Merging($\mathcal{A}$, $\mathcal{T}$)

2: $\mathcal{T}^{\prime}\leftarrow\mathcal{T}$

3: for $N\in\mathcal{A}$ do

4: for $n\in\mathcal{T}^{\prime}$ do $\triangleright$ Prefixing
$\mathcal{T}^{\prime}$

5: $n.\alpha=N.\alpha\oplus n.\alpha$ $\triangleright$ Prefixing the pattern
with $N.\alpha$

6: for all $I\in n.\mathcal{I}$ do $\triangleright$ Prefixing all occurrences

7: $I=d\cup I$$\triangleright$ $d$ is the last element of $N.\mathcal{I}$

8: end for

9: end for

10: RecMerge($\mathcal{T}^{\prime}$, $N$) $\triangleright$ Recursive merging
of $\mathcal{T}^{\prime}$ with nodes $N$ of $\mathcal{A}$

11: end for

12: return $\mathcal{A}$

13:end function

Let $N.\alpha$ be the pattern associated with a node $N$ from the tree of
patterns $\mathcal{A}$ and $N.\mathcal{I}$ be the list of occurrences
associated with $N$. For each node $N$ of $\mathcal{A}$, the itemset tree
$\mathcal{T}$ is first prefixed by $N$: on the one hand, the patterns of each
node of $\mathcal{T}$ are prefixed by $N.\alpha$; on the other hand, all
occurrences of $\mathcal{T}$ are prefixed by the last occurrence of
$N.\mathcal{I}$. Using the last occurrence in $N.\mathcal{I}$ enforces the
third property (see eq. 1).

Algorithm 2 RecMerge: recursively merging the prefixed itemset tree
$\mathcal{T}$ with a node of $\mathcal{A}$

1:$n$: itemset node tree, $N$: node of the tree of patterns to be merged with
$n$ and such that $n.\alpha=N.\alpha$

2:function RecMerge($n$, $N$)

3: $N.\mathcal{I}\leftarrow N.\mathcal{I}\cup n.\mathcal{I}$ $\triangleright$
Merging lists of occurrences

4: for $s_{N}\in N.\mathcal{S}\cup N.\mathcal{C}$ do $\triangleright$
Recursion

5: for $s_{n}\in n.\mathcal{S}\cup n.\mathcal{C}$ do

6: if $s_{N}.\alpha=s_{n}.\alpha$ then

7: $found\leftarrow\texttt{True}$

8: RecMerge($s_{n}$, $s_{N}$)

9: end if

10: end for

11: if not $found$ then

12: if $s_{n}\in n.\mathcal{S}$ then

13: $N.\mathcal{S}\leftarrow N.\mathcal{S}\cup\\{$Copy($s_{n}$)$\\}$

14: else

15: $N.\mathcal{C}\leftarrow N.\mathcal{C}\cup\\{$Copy($s_{n}$)$\\}$

16: end if

17: end if

18: end for

19:end function

In a second step, the algorithm recursively merges the root of the itemset
tree $\mathcal{T}$ prefixed by $N$. Algorithm 2 details this merging
operation. We first need to make sure that $n.\alpha=N.\alpha$ to verify that
the two nodes represent the same pattern. At line 3, occurrences of nodes $n$
and $N$ are merged. By construction of the new occurrence, the conditions of
Eq. 1 are satisfied. Then, the descendants of $n$ are processed recursively.
For each node of $n.\mathcal{S}$ (resp. $n.\mathcal{C}$), we search a node
$s_{n}$ in $N.\mathcal{S}$ (resp. $N.\mathcal{C}$) such that these nodes
represent the same pattern. If such a node is found, then the function
RecMerge is recursively applied. Otherwise, a copy of the entire subtree of
$s_{n}$ is added to $n.\mathcal{S}$ (resp. $n.\mathcal{C}$).

###  3.3 Completion of a list of occurrences

When a new pattern is introduced in the tree, it means that it was unfrequent
in the previous window, but there might exist occurrences of this pattern.
They were simply not stored in the tree (except quasi-frequent patterns). For
example, in Figure 2, the pattern $\langle bc\rangle$ (node surrounded by a
dotted line square) is not frequent in $W$ and is not present in the frequent
patterns tree $\mathcal{A}_{2}(W)$. However, after the arrival of itemset
$(bc)$ the pattern $\langle bc\rangle$ may become frequent in $W$. Thus, it is
necessary to scan $W^{\prime}$ to retrieve all occurrences of $\langle
bc\rangle$ to compute its frequency.

The completion algorithm is applied exclusively to the nodes newly introduced
in the tree. While ensuring the completeness, this method reduces the number
of completions. In addition, to make the completion efficient, the occurrences
of a pattern $\beta$ is recursively constructed from the occurrences of its
direct parent along the following principles:

  * •

each occurrence $I=(i_{1},\dots,i_{|\delta|})$ of a pattern $\delta$ obtained
by adding an item $e$ to the last itemset of $\beta$ (composition) are
necessarily occurrences of $\beta$, thus the algorithm tests whether $e$ is
included in the itemset $w_{i_{|\delta|}}$.

  * •

each occurrence $I=(i_{1},\dots,i_{|\epsilon|})$ of a pattern $\epsilon$,
obtained by adding an itemset $e$ to $\beta$ (succession), are necessarily
constructed by adding the element $i_{|\epsilon|}$ to an occurrence of
$\beta$, thus the algorithm browses a sub-sequence of $W^{\prime}$ to test the
presence of $e$.

For succession nodes, the completion scans only the sub-sequence of
$W^{\prime}$ composed of the itemsets between $i_{|\beta|}+1$ and
$j_{|\beta|-1}$, where $J=(j_{1},\dots,j_{|\beta|})$ is the occurrence after
$I$ in the list of occurrences of $\beta$.

As an example, on the tree $\mathcal{A}^{c}$ in Figure 2, the occurrences of
$\langle bc\rangle$ is $\mathcal{I}(\langle bc\rangle)=\\{(3,5)\\}$. This
occurrence has been obtained in the merging step by adding the element $5$ to
the occurrence $(3)$ of pattern $\langle b\rangle$. An occurrence of
$\mathcal{I}(\langle bc\rangle)$ is the successor of one of the occurrences of
$\langle b\rangle$: $\mathcal{I}(\langle b\rangle)=\\{(2),(3),(5)\\}$. To
complete occurrence $(3)$ from $\mathcal{I}(\langle b\rangle)$, the algorithm
looks for one $c$ in $W^{\prime}$ at a position between $3$ ($=2+1$) and the
beginning of the third occurrence of $\mathcal{I}(\langle b\rangle)$, _i.e._
$5$. Here, occurrence $(3,4)$ is found. But it is a sub-sequence of an
existing occurrence $(3,5)$. Due to the definition of minimal occurrences (eq.
1), $(3,5)$ is deleted. The same for pattern $(ab)c$ (the other node
surrounded by a dotted line square). It is not possible to complete occurrence
$(2)$ of $\mathcal{I}(\langle b\rangle)$ because there is no $c$ in the
itemset at position $3$ (the only possible itemset between the occurrence of
$\langle b\rangle$ at position ($2$) and the next occurrence in
$\mathcal{I}(\langle bc\rangle)$).

It is worth mentioning that the proposed algorithm is complete. Specifically,
in a streaming context which applies recursively the incremental mining
process, it extracts all the frequent sequential patterns for each sliding
window of the stream.

##  4 Experiments and results

The objective of our experiments is to show that the proposed algorithm is an
efficient strategy for mining sequential patterns incrementally. More
specifically, we would like to assess the space and time efficiency of the
proposal compared to a $Batch$ approach, _i.e._ a strategy that do not exploit
the incremental changes of the window. The $Batch$ algorithm is based on
PrefixSpan uses the PSP tree structure. It rebuilds the entire tree
$\mathcal{A}_{\sigma}(W)$ for each consecutive window of size $ws$ on the data
stream. To the best of our knowledge, there is no state-of-the-art competitor
for this task.

It is worth noticing that the two approaches are complete and thus extract the
exact same sets of patterns. For this reason, we do not discuss the algorithm
outputs but only their efficiency.

In a first experiment, we present the result on synthetic data which have been
widely used to evaluate the efficiency of sequential pattern mining
algorithms. As the purely random nature of this data does not mimic the
characteristics of true datasets (with less balanced itemset occurrences or
with the presence of significant patterns), we supplement this experiment with
an experiment on a real dataset. This dataset also illustrates the practical
value and additional information gained by addressing the newly formulated
sequential pattern mining problem of this work.

The algorithms were implemented in C++ and ran on a single core. The source
code, synthetic datasets and benchmarks scripts are available
online333https://gitlab.inria.fr/tguyet/seqstreamminer.

###  4.1 Experiments on synthetic data

In this section, we evaluate IncSeq against $Batch$ on synthetic datasets
generated in the same way as the IBM quest data generator. Specifically, at
each sequence position, an item is present with a probability of 3%, thus
yielding a random sequence of itemsets. The length of the sequence simulating
the stream is 1000 times of the windows size, which requires the incremental
algorithm to be recursively called 1000 times in a run. The item vocabulary
size, $card(\mathcal{E})$, is set to 40. Then, the average number of items per
itemset is $1.2$. The experiments were conducted by varying the parameters
$ws$ (window size from 80 to 300) and $\sigma$ (minimal support from 3 to 10
occurrences) on 5 different datasets per configuration. The results reported
are the average results of all the experiments.

(a)  (b)

(c)  (d)

Figure 3: Comparison of processing time (logarithmic scale) and memory usage
with respect to the support threshold $\sigma$ (with $ws<25$) and the size of
the sliding window $ws$. (c) and (d) represent the respective computing time
ratio of Batch to IncSeq on the same dataset.

Figure 3-(a) illustrates the execution time with respect to $\sigma$. As one
can see, the execution time grows exponentially when $\sigma$ decreases. Note
that a timeout is set as 10 minutes. For more time-consuming mining tasks
(with low $\sigma$), Batch failed 17 times before a successful completion of
the mining process, while IncSeq failed 16 times. It is also clear that
IncSeq, on average, is an order of magnitude faster than $Batch$. To further
assess the superior efficiency of IncSeq on mining various sizes of window,
Figure 3-(c) and (d) provide the execution time ratio between IncSeq and
$Batch$ with respect to $\sigma$ and $ws$, respectively. As one can see,
IncSeq dominates $Batch$ by 10 to 20 times faster in processing time when
$\sigma$ and $ws$ increase. The different drop for $\sigma=10$ because the
number of frequent patterns is closed to zero. Thus, the computing times are
very low for the two approaches.

Figure 3-(b) additionally shows the memory usage of the two approaches. As
expected, the two approaches are comparable in terms of the memory usage as
the required memory is mainly to store the frequent sequential patterns and
the two approaches induce identical trees. We also observe that the memory
requirement depends upon $\sigma$ as the lower $\sigma$ the more frequent
patterns. Ensuring memory efficiency is also an essential prerequisite for
sequential pattern mining, our proposed method therefore enjoys the advantage
of mining sequential patterns with reduced time at no extra memory cost.

###  4.2 Experiments on smart electrical meter data

Figure 4: Comparison of computation time (left) and memory usage (right) when
mining the power consumption streams.

We also conducted experiments on real smart electrical meter data. Smart
electrical meters record the power consumption of an individual or company in
intervals of 30 min and communicate that “instant” information to the electric
provider for monitoring and billing purposes. The aim of smart meters is to
better anticipate the high consumption of a distribution sector by awarding a
consumption profile to each meter, _i.e._ a dynamic model of changes in
consumption. As consumption profiles depend on the period of year (seasons,
holidays), week (weekdays, weekends) or day and are unpredictable for medium
to long-term consumption, we employ IncSeq and $Batch$ to extract the dynamic
online profiles of short-term consumption of the meters.

The annual series of instantaneous consumption is a flow of about 18,000
values. We use the SAX algorithm [10] for discretizing the consumption values.
A vocabulary size of $|\mathcal{E}|=14$ and a window aggregation of $PAA=24$
have been chosen. The consumption profile of a smart meter at time $t$ is the
set of frequent consumption patterns during the period $[t-w,t]$ (sliding
window of predefined size $w=28$ itemsets, _i.e._ 2 weeks).

Figure 4 shows the results for 40 meters. It is clear that the results
obtained on the real data are consistent with those obtained on synthetic
data. Specific to the real data, while most of the meters can be processed
within seconds, the processing time of some meters are significantly longer
(about few minutes). This disparity is attributed to the observed consumption
variability. Specifically, the patterns that are more time-consuming to
process are relative constant (_e.g._ industrial consumption) consisting of
many repetitions of symbols, thus lead to a large tree depth. It is however
clear the results of real and synthetic datasets conclusively match, which
suggests that our proposed method is an efficient sequential pattern miner
with manageable memory cost.

##  5 Related work

In the field of stream mining, several approaches extended frequent pattern
mining in a setting similar to ours. For example, Chang et al. [3] proposed to
extract recent frequent patterns in a sliding window over a data stream, while
Calders et al. [2] improved such approaches with the adaptive window size.
More recently, Giacometti and Soulet [5] proposed a sampling of the pattern to
improve the efficiency. Our approach focuses on more complex patterns, i.e.,
sequential patterns, to extract additional information with a similar
streaming setup.

For sequential patterns, less efforts have been made in streaming settings
[4]. The incremental or online sequential pattern mining algorithms in the
literature address simplified problems of ours: mining frequent sequential
patterns in a stream of transaction that are sequences, such as IncSPAM [7],
or mining frequent sequential patterns in a collection of itemsets streams,
such as PSP-AMS [8]; in both cases, the counting of sequential pattern is
based on the number of transactions (resp. number of streams) in which a
pattern occurs. However, all these algorithms examine the existence of a
pattern in each transaction as the pattern counting method and ignore the
multiple occurrences of the pattern in a transaction. Tseng et _al._ [16]
share the similar objective, but their mining algorithms are not incremental.
Their framework combines the results of episode mining by batches in a map-
reduce architecture without the formal properties of IncSeq.

Finally, our approach is also different from single-pass serial episodes
mining algorithms [9] whose objective is not to maintain the set of frequent
serial-episodes, but is to evaluate the support of serial episodes online.

##  6 Conclusion

Although a number of studies have developed approaches to mine sequential
patterns over data streams, all of these techniques focus on a stream of items
and the number of transactions that contain the pattern without considering
its multiple occurrences. In this work, we present our incremental algorithm
based on counting the minimal occurrences of the sequential patterns over the
course of itemsets stream. Experimental studies indicate the superior
computational efficiency of our approach compared to the non-incremental
method. In the future, we plan to further extend it by considering the
condensed representation such as maximum patterns and closed patterns in the
context of incremental mining.

## References

  * [1] A. Achar, S. Laxman, and P. S. Sastry, _A unified view of automata-based algorithms for frequent episode discovery_ , CoRR abs/1007.0690 (2010).
  * [2] Toon Calders, Nele Dexters, Joris JM Gillis, and Bart Goethals, _Mining frequent itemsets in a stream_ , Information Systems 39 (2014), 233–255.
  * [3] Joong Hyuk Chang and Won Suk Lee, _A sliding window method for finding recently frequent itemsets over online data streams_ , Journal of Information science and Engineering 20 (2004), no. 4, 753–762.
  * [4] Philippe Fournier-Viger, Jerry Chun-Wei Lin, Rage Uday Kiran, Yun Sing Koh, and Rincy Thomas, _A survey of sequential pattern mining_ , Data Sc. Pat. Reco. 1 (2017), no. 1, 54–77.
  * [5] Arnaud Giacometti and Arnaud Soulet, _Reservoir pattern sampling in data streams_ , Proc. ECML-PKDD, 2021, pp. 337–352.
  * [6] Thomas Guyet and René Quiniou, _Incremental mining of frequent sequences from a window sliding over a stream of itemsets_ , Actes IAF (2012).
  * [7] Chin-Chuan Ho, Hua-Fu Li, Fang-Fei Kuo, and Suh-Yin Lee, _Incremental mining of sequential patterns over a stream sliding window_ , International Conference on Data Mining-Workshops (ICDMW), 2006, pp. 677–681.
  * [8] Bijay Prasad Jaysawal and Jen-Wei Huang, _Psp-ams: Progressive mining of sequential patterns across multiple streams_ , ACM Trans. Knowl. Discov. Data 13 (2018), no. 1, 1–23.
  * [9] Hui Li, Sizhe Peng, Jian Li, Jingjing Li, Jiangtao Cui, and Jianfeng Ma, _Counting the frequency of time-constrained serial episodes in a streaming sequence_ , Information Sciences 505 (2019), 422–439.
  * [10] J. Lin, E. Keogh, S. Lonardi, and B. Chiu, _A symbolic representation of time series, with implications for streaming algorithms_ , Proceedings of the Workshop on Research Issues in Data Mining and Knowledge Discovery, 2003.
  * [11] H. Mannila, H. Toivonen, and A. I. Verkamo, _Discovering frequent episodes in event sequences_ , Journal of Data Mining and Knowledge Discovery 1 (1997), no. 3, 210–215.
  * [12] F. Masseglia, F. Cathala, and P. Poncelet, _The PSP approach for mining sequential patterns_ , Proceedings of the European Symposium on Principles of Data Mining and Knowledge Discovery, 1998, pp. 176–184.
  * [13] J. Pei, J. Han, B. Mortazavi-Asl, J. Wang, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu, _Mining sequential patterns by pattern-growth: the PrefixSpan approach_ , Transactions on Knowledge and Data Engineering 16 (2004), no. 11, 1424–1440.
  * [14] R. Srikant and R. Agrawal, _Mining sequential patterns: Generalizations and performance improvements_ , Proceedings of the International Conference on Extending Database Technology, 1996, pp. 3–17.
  * [15] Nikolaj Tatti and Boris Cule, _Mining closed strict episodes_ , Data Mining and Knowledge Discovery 25 (2012), no. 1, 34–66.
  * [16] Jerry C. C. Tseng, Jia-Yuan Gu, P. F. Wang, Ching-Yu Chen, Chu-Feng Li, and Vincent S. Tseng, _A scalable complex event analytical system with incremental episode mining over data streams_ , Proc. of Congress on Evolutionary Computation, 2016, pp. 648–655.
  * [17] Morteza Zihayat, Cheng-Wei Wu, Aijun An, Vincent S Tseng, and Chien Lin, _Efficiently mining high utility sequential patterns in static and streaming data_ , Proc. of Intelligent Data Analysis, vol. 21, 2017, pp. 103–135.


$\displaystyle\kappa_{3,\mathrm{pair}}=n^{3/2}E\left\\{\frac{(\hat{\tau}-\tau)^{3}}{\sigma^{3}}\right\\}-3\sqrt{n}E\left(\frac{\hat{\tau}-\tau}{\sigma}\frac{\hat{\sigma}_{\mathrm{pair}}^{2}-\sigma_{\mathrm{pair}}^{2}}{\sigma_{\mathrm{pair}}^{2}}\right)+O\left(n^{-1}\right),$

we have

$\displaystyle\gamma_{1,\mathrm{pair}}$
$\displaystyle=\kappa_{1,\mathrm{pair}}=-\frac{\sqrt{n}}{2}E\left(\frac{\hat{\tau}-\tau}{\sigma}\frac{\hat{\sigma}_{\mathrm{pair}}^{2}-\sigma_{\mathrm{pair}}^{2}}{\sigma_{\mathrm{pair}}^{2}}\right)+O\left(n^{-1}\right),$
$\displaystyle\gamma_{2,\mathrm{pair}}$
$\displaystyle=\frac{\kappa_{2,\mathrm{pair}}-1+\kappa_{1,\mathrm{pair}}^{2}}{2}=O(n^{-1}),$
$\displaystyle\gamma_{3,\mathrm{pair}}$
$\displaystyle=\frac{\kappa_{3,\mathrm{pair}}+3\kappa_{1,\mathrm{pair}}\kappa_{2,\mathrm{pair}}-3\kappa_{1,\mathrm{pair}}+\kappa_{1,\mathrm{pair}}^{3}}{6}$
$\displaystyle=\frac{n^{3/2}}{6}E\left\\{\frac{(\hat{\tau}-\tau)^{3}}{\sigma^{3}}\right\\}-\frac{\sqrt{n}}{2}E\left(\frac{\hat{\tau}-\tau}{\sigma}\frac{\hat{\sigma}_{\mathrm{pair}}^{2}-\sigma_{\mathrm{pair}}^{2}}{\sigma_{\mathrm{pair}}^{2}}\right)+O\left(n^{-1}\right).$

We further know that
$\gamma_{l,\mathrm{pair}}\asymp\gamma_{l,\mathrm{pair}}^{\prime}=O(n^{\lfloor
l/3\rfloor-l/2})$ for $l\geq 4$, and then the Edgeworth expansion for
$T_{\mathrm{pair}}$ is

$\displaystyle\mathrm{pr}(T_{\mathrm{pair}}\leq t)$
$\displaystyle=\Phi(t)+\frac{\sqrt{n}}{2}E\left(\frac{\hat{\tau}-\tau}{\sigma}\frac{\hat{\sigma}_{\mathrm{pair}}^{2}-\sigma_{\mathrm{pair}}^{2}}{\sigma_{\mathrm{pair}}^{2}}\right)t^{2}\phi(t)-\frac{n^{3/2}E(\hat{\tau}-\tau)^{3}}{6\sigma^{3}}(t^{2}-1)\phi(t)+o\left(n^{-1/2}\right).$

∎

##  S11 Proof of Theorem 8

###### Proof of Theorem 8.

The Cornish-Fisher expansion can be expressed as
$q_{\alpha}=z_{\alpha}+p(z_{\alpha})+o(n^{-1/2})$, where $p(z_{\alpha})$ is a
function of $z_{\alpha}$ and $p(z_{\alpha})=O(n^{-1/2})$. According to Theorem
7, we have

$\displaystyle\alpha$ $\displaystyle=\mathrm{pr}(T\leq q_{\alpha})$
$\displaystyle=\Phi(q_{\alpha})+\frac{\sqrt{n}}{2}E\left(\frac{\hat{\tau}-\tau}{\sigma}\frac{\hat{\sigma}_{\mathrm{pair}}^{2}-\sigma_{\mathrm{pair}}^{2}}{\sigma_{\mathrm{pair}}^{2}}\right)q_{\alpha}^{2}\phi(q_{\alpha})-\frac{n^{3/2}E(\hat{\tau}-\tau)^{3}}{6\sigma^{3}}(q_{\alpha}^{2}-1)\phi(q_{\alpha})+O\left(n^{-1}\right).$

According to Taylor’s expansion, we have

$\displaystyle\Phi(q_{\alpha})$
$\displaystyle=\Phi\\{z_{\alpha}+p(z_{\alpha})+o(n^{-1/2})\\}=\Phi(z_{\alpha})+p(z_{\alpha})\phi(z_{\alpha})+o(n^{-1/2}),$
$\displaystyle q_{\alpha}^{2}\phi(q_{\alpha})$
$\displaystyle=z_{\alpha}^{2}\phi(z_{\alpha})+p(z_{\alpha})(2z_{\alpha}-z_{\alpha}^{3})\phi(z_{\alpha})+o(n^{-1/2}),$

and

$\displaystyle\phi(q_{\alpha})$
$\displaystyle=\phi(z_{\alpha})-p(z_{\alpha})z_{\alpha}^{3}\phi(z_{\alpha})+o(n^{-1/2}).$

Comparing both sides of the equality, we have

$\displaystyle
p(z_{\alpha})+\frac{\sqrt{n}}{2}E\left(\frac{\hat{\tau}-\tau}{\sigma}\frac{\hat{\sigma}_{\mathrm{pair}}^{2}-\sigma_{\mathrm{pair}}^{2}}{\sigma_{\mathrm{pair}}^{2}}\right)z_{\alpha}^{2}\phi(z_{\alpha})-\frac{n^{3/2}E(\hat{\tau}-\tau)^{3}}{6\sigma^{3}}(z_{\alpha}^{2}-1)\phi(z_{\alpha})=0,$

which implies that

$\displaystyle
p(z_{\alpha})=-\frac{\sqrt{n}}{2}E\left(\frac{\hat{\tau}-\tau}{\sigma}\frac{\hat{\sigma}_{\mathrm{pair}}^{2}-\sigma_{\mathrm{pair}}^{2}}{\sigma_{\mathrm{pair}}^{2}}\right)z_{\alpha}^{2}\phi(z_{\alpha})+\frac{n^{3/2}E(\hat{\tau}-\tau)^{3}}{6\sigma^{3}}(z_{\alpha}^{2}-1)\phi(z_{\alpha}).$

Therefore, the Cornish-Fisher expansion is

$\displaystyle
q_{\alpha}=z_{\alpha}-\frac{\sqrt{n}}{2}E\left(\frac{\hat{\tau}-\tau}{\sigma}\frac{\hat{\sigma}_{\mathrm{pair}}^{2}-\sigma_{\mathrm{pair}}^{2}}{\sigma_{\mathrm{pair}}^{2}}\right)z_{\alpha}^{2}\phi(z_{\alpha})+\frac{n^{3/2}E(\hat{\tau}-\tau)^{3}}{6\sigma^{3}}(z_{\alpha}^{2}-1)\phi(z_{\alpha})+o(n^{-1/2}).$

∎

##  S12 Proof of Theorem 9

###### Proof of Theorem 9.

We mainly focus on two terms. First, we calculate

$\displaystyle
E\left\\{(\hat{\tau}-\tau)(\hat{\tau}_{[m]}-\hat{\tau})^{2}\right\\}$
$\displaystyle=2\left\\{\frac{(\tau_{[m]}-L_{[m]})^{2}}{M}-\frac{\sigma^{2}}{n}\right\\}(\tau_{[m]}-\tau),$

where $L_{[m]}=Y_{[m]2}(1)-Y_{[m]1}(0)$. Under the definition of $L_{[m]}$,
$\hat{\tau}_{[m]}=2Z_{[m]1}(\tau_{[m]}-L_{[m]})-L_{[m]}$,
$\hat{\tau}_{[m]}-\tau_{[m]}=(2Z_{[m]1}-1)(\tau_{[m]}-L_{[m]})$ and
$\sigma^{2}=2M^{-1}\sum_{m=1}^{M}(\tau_{[m]}-L_{[m]})^{2}$. Then,

$\displaystyle
E\left(\frac{\hat{\tau}-\tau}{\sigma}\frac{\hat{\sigma}_{\mathrm{pair}}^{2}-\sigma_{\mathrm{pair}}^{2}}{\sigma_{\mathrm{pair}}^{2}}\right)$
$\displaystyle=\frac{n^{3/2}}{M(M-1)}\sum_{m=1}^{M}E\left\\{\frac{(\hat{\tau}-\tau)(\hat{\tau}_{[m]}-\hat{\tau})^{2}}{\sigma\sigma_{\mathrm{pair}}^{2}}\right\\}$
$\displaystyle=\sum_{m=1}^{M}\frac{2n^{3/2}(\tau_{[m]}-L_{[m]})^{2}(\tau_{[m]}-\tau)}{M^{2}(M-1)\sigma\sigma_{\mathrm{pair}}^{2}}.$

When $\tau_{[m]}-\tau=o(1)$, the right hand side is $o(n^{-1/2})$. Another
calculation shows that

$\displaystyle(\hat{\tau}-\tau)^{3}$
$\displaystyle=\left\\{\frac{1}{M}\sum_{m=1}^{M}(2Z_{[m]1}-1)(\tau_{[m]}-L_{[m]})\right\\}^{3}=\frac{1}{M^{3}}\sum_{m=1}^{M}(2Z_{[m]1}-1)^{3}(\tau_{[m]}-L_{[m]})^{3}.$

Its expectation is 0 as $E(2Z_{[m]1}-1)^{3}=0$, which implies that

$\displaystyle\frac{E(\hat{\tau}-\tau)^{3}}{6\sigma^{3}}=0.$

In the bootstrap procedure, $\tau_{[m]}^{*}=\tau^{*}=0$ and then

$\displaystyle
E^{*}\left\\{\frac{\hat{\tau}^{*}-\tau^{*}}{\sigma^{*}}\frac{(\hat{\sigma}_{\mathrm{pair}}^{*})^{2}-(\sigma_{\mathrm{pair}}^{*})^{2}}{(\sigma_{\mathrm{pair}}^{*})^{2}}\right\\}=\frac{E^{*}(\hat{\tau}^{*}-\tau^{*})^{3}}{6(\sigma^{*})^{3}}=0.$

We then finish the proof. ∎

##  S13 Proof of Remark 1

Step 1 for rank-preserving imputation is essentially equivalent to generating
two new samples of size $n$ by including $n_{[m]z}^{j}$ copies of the $j$th
largest unit from the observed outcomes in each group. Here,

$\displaystyle n_{[m]z}^{j}=\left\lceil
jn_{[m]z}^{-1}n_{[m]}\right\rceil-\left\lceil(j-1)n_{[m]z}^{-1}n_{[m]}\right\rceil,\quad
z=0,1,\quad j=1,2,\cdots,n_{[m]z},$

where $\lceil\cdot\rceil$ represents the ceiling function.

Recall that, in each stratum, we impute the unobserved outcomes such that the
imputed $Y_{i}^{\mathrm{imp}}(1)$ and $Y_{i}^{\mathrm{imp}}(0)$ are co-
monotonic. For $i\in[m]$,

$\displaystyle Y_{i}^{\mathrm{imp}}(0)=\begin{cases}Y_{i}&\text{ if
}Z_{i}=0,\\\ \hat{F}_{[m]}^{-1}\left\\{\hat{G}_{[m]}(Y_{i})\right\\}&\text{
otherwise, }\end{cases}$ $\displaystyle
Y_{i}^{\mathrm{imp}}(1)=\begin{cases}Y_{i}&\text{ if }Z_{i}=1,\\\
\hat{G}_{[m]}^{-1}\left\\{\hat{F}_{[m]}(Y_{i})\right\\}&\text{ otherwise.
}\end{cases}$

We will show that the above procedure is equivalent to generating two new
samples of size $n$ by including $n_{[m]z}^{j}$ copies of the $j$th biggest
unit of the observed outcomes in each group.

###### Proof.

For any $m=1,...,M$, without loss of generality, we suppose that (i) $i\in[m]$
for $i=1,...,n_{[m]}$; (ii) $n_{[m]z}\leq n_{[m]1-z}$; (iii) $Z_{i}=z$ for
$i=1,...,n_{[m]z}$ and $Z_{i}=1-z$ for $i=n_{[m]z}+1,...,n_{[m]}$; (iv)
$Y_{1}(z)\leq\cdots\leq Y_{n_{[m]z}}(z)$ and
$Y_{n_{[m]z}+1}(1-z)\leq\cdots\leq Y_{n_{[m]}}(1-z)$.

For $i=n_{[m]z}+k$ with $k=1,\cdots,n_{[m]1-z}$,

$\displaystyle Y_{i}^{\mathrm{imp}}(z)$
$\displaystyle=I(z=1)\hat{G}_{[m]}^{-1}[\hat{F}_{[m]}\\{Y_{n_{[m]1}+k}(0)\\}]+I(z=0)\hat{F}_{[m]}^{-1}[\hat{G}_{[m]}\\{Y_{n_{[m]0}+k}(1)\\}]$
$\displaystyle=Y_{\lceil kn_{[m]1-z}^{-1}n_{[m]z}\rceil}(z).$

Now we consider $k$ satisfies $\lceil(k+1)n_{[m]1-z}^{-1}n_{[m]z}\rceil-\lceil
kn_{[m]1-z}^{-1}n_{[m]z}\rceil=1$. Under this circumstance,
$\lceil(k+1)n_{[m]1-z}^{-1}n_{[m]z}\rceil\neq\lceil
kn_{[m]1-z}^{-1}n_{[m]z}\rceil$ and $Y_{\lceil
kn_{[m]1-z}^{-1}n_{[m]z}\rceil}(z)$ will change. We solve the equation and get
$k_{j}=\lceil jn_{[m]z}^{-1}n_{[m]1-z}\rceil-1$, where $j=1,\cdots,n_{[m]z}$.
So the number of copies of $Y_{j}(z)$ is $1+k_{j}-k_{j-1}=1+(\lceil
jn_{[m]z}^{-1}n_{[m]1-z}\rceil-1)-(\lceil(j-1)n_{[m]z}^{-1}n_{[m]1-z}\rceil-1)=\lceil
jn_{[m]z}^{-1}n_{[m]}\rceil-\lceil(j-1)n_{[m]z}^{-1}n_{[m]}\rceil$ for
$j=1,\cdots,n_{[m]z}$.

When $i=k^{\prime}$ with $k^{\prime}=1,\cdots,n_{[m]z}$,

$Y_{i}^{\mathrm{imp}}(1-z)=\hat{F}_{[m]}^{-1}\\{\hat{G}_{[m]}(Y_{k^{\prime}}(z))\\}=Y_{\lceil
k^{\prime}n_{[m]z}^{-1}n_{[m]1-z}\rceil+n_{[m]z}}(1-z).$

As $n_{[m]1-z}\geq n_{[m]z}$, only when there exist
$j^{\prime}\in\\{1,\cdots,n_{[m]z}\\}$,
$k^{\prime}\in\\{1,\cdots,n_{[m]1-z}\\}$ and $\lceil
k^{\prime}n_{[m]z}^{-1}n_{[m]1-z}\rceil=j^{\prime}$, there is another copy of
$Y_{j^{\prime}}(1-z)$. At this time,
$(j^{\prime}-1)n_{[m]1-z}^{-1}n_{[m]z}\leq
k^{\prime}<j^{\prime}n_{[m]1-z}^{-1}n_{[m]z}$, so the number of copies of
$Y_{j^{\prime}}(1-z)$ is $1+\lceil
j^{\prime}n_{[m]1-z}^{-1}n_{[m]z}\rceil-\lceil(j^{\prime}-1)n_{[m]1-z}^{-1}n_{[m]z}\rceil=\lceil
j^{\prime}n_{[m]1-z}^{-1}n_{[m]}\rceil-\lceil(j^{\prime}-1)n_{[m]1-z}^{-1}n_{[m]}\rceil$.

Finally, we prove that $Y_{i}^{\mathrm{imp}}(1)$ and $Y_{i}^{\mathrm{imp}}(0)$
are co-monotonic. For $i=1,\cdots,n_{[m]z}$, the imputed $Y_{i}(1-z)$ is
$Y_{\lceil in_{[m]z}^{-1}n_{[m]1-z}\rceil+n_{[m]z}}(1-z)$. For
$k=1,\cdots,n_{[m]1-z}$, the imputed outcome of $Y_{k+n_{[m]z}}(1-z)$ is
$Y_{i}(z)$ if and only if $\lceil kn_{[m]1-z}^{-1}n_{[m]z}\rceil=i$. Above
all, in the imputed population, the matched outcomes of $Y_{i}(z)$ is
$\\{Y_{r_{i}+n_{[m]z}}(1-z)\\}$, where $r_{i}$ is a positive integer and
satisfies $(i-1)n_{[m]z}^{-1}n_{[m]1-z}<r_{i}\leq in_{[m]z}^{-1}n_{[m]1-z}$.
It means $\max(r_{i})\leq\min(r_{i+1})$ for $i=1,\cdots,n_{[m]z}$. Then,
$Y_{i}^{\mathrm{imp}}(1)$ and $Y_{i}^{\mathrm{imp}}(0)$ are co-monotonic. ∎

## References

  * Aronow et al., (2014) Aronow, P. M., Green, D. P., and Lee, D. K. K. (2014).  Sharp bounds on the variance in randomized experiments.  Annals of Statistics, 42(3):850–871.
  * Bloznelis and Götze, (2002) Bloznelis, M. and Götze, F. (2002).  An edgeworth expansion for symmetric finite population statistics.  Annals of Probability, 30(3):1238–1265.
  * Bobkov, (2004) Bobkov, S. G. (2004).  Concentration of normalized sums and a central limit theorem for noncorrelated random variables.  Annals of Probability, 32(4):2884–2907.
  * Hall, (2013) Hall, P. (2013).  The bootstrap and Edgeworth expansion.  Springer Science & Business Media.
  * Imbens and Menzel, (2021) Imbens, G. and Menzel, K. (2021).  A causal bootstrap.  Annals of Statistics, 49(3):1460–1488.
  * Lehmann, (1966) Lehmann, E. L. (1966).  Some concepts of dependence.  The Annals of Mathematical Statistics, 37(5):1137–1153.
  * Liu and Yang, (2020) Liu, H. and Yang, Y. (2020).  Regression-adjusted average treatment effect estimates in stratified randomized experiments.  Biometrika, 107(4):935–948.
  * Tchen, (1980) Tchen, A. H. (1980).  Inequalities for distributions with given marginals.  Annals of Probability, 8(4):814–827.
  * Zhu et al., (2021) Zhu, K., Liu, H., and Yang, Y. (2021).  Design-based theory for lasso adjustment in randomized block experiments with a general blocking scheme.  arXiv preprint arXiv:2109.11271.


# Frontrunning Block Attack in PoA Clique:
A Case Study††thanks: This work was in part presented at IEEE ICBC 2022.

Xinrui Zhang 1, Qin Wang 3, Rujia Li 12, Qi Wang 1ð 1 Southern University of
Science and Technology, China.
$\eth$: Corresponding author. 2 University of Birmingham, United Kingdom.
3 CSIRO Data61, Australia.

###### Abstract

As a fundamental technology of decentralized finance (DeFi), blockchain’s
ability to maintain a distributed fair ledger is threatened by manipulation of
block/transaction order. In this paper, we propose a frontrunning block attack
against the Clique-based Proof of Authority (PoA) algorithms. Our attack can
frontrun blocks from honest in-turn sealers by breaking the proper order of
leader selection. By falsifying the priority parameters (both difficulty and
delay time), a malicious out-of-turn sealer can always successfully occupy the
leader position and produce advantageous blocks that may contain profitable
transactions. As a typical instance, we apply our attack to a mature Clique-
engined project, HPB ($3,058,901, as of April 2022). Experimental results
demonstrate the effectiveness and feasibility. Then, we further recommend
fixes that make identity checks effective. Our investigation and suggestion
have been submitted to its official team and got their approval. We believe
this work can act as, at least, a warning case for Clique variants to avoid
repeating these design mistakes.

###### Index Terms:

Proof of Authority, Clique, Frontrunning Attack

##  I Introduction

Proof of Authority (PoA) consensus algorithm was first proposed by Wood [1][2]
and further used in Geth [3] and Parity [4]. As an implementation of PoA
algorithms, Clique has become a mainstream design since it is merged into the
Ethereum mainnet [5]. Clique relies on a limited number of authorities
(denoted by sealers) and their reputation to achieve consensus. Instead of
selecting one mining leader in each round, Clique allows multiple sealers to
produce blocks in parallel with different priorities. This mechanism makes
Clique only process one round of messages across multiple sealers. Fewer
message exchanges result in faster confirmation and better performance. Owing
to those advantages, Clique has recently emerged as one of the most prevailing
consensus algorithms and inspires many variants that have been applied to
well-known projects (cf. Table IV), such as GoChain [6], Binance chain [7],
POA network [8] and ConsenSys [9].

In the original design of Clique, a set of sealers are allowed to propose
blocks in the same epoch, where an in-turn sealer (equiv. leader) proposes the
first-priority block, while edge-turn sealers create second-priority blocks
with a random delay (cf. Figure 1.(a)). Since more than one blocks are
created, forks may occur. Clique adopts a simplified version of GHOST protocol
[10][11] to select branches. A higher priority ensures that a block is more
likely to be included in the final chain. Under the default assumption of
Clique, the majority of sealers are honest. An in-turn sealer is elected each
round in a round-robin way. This is inherently determined by a predefined
formula combining the block index and the number of sealers. For more details,
see example [12][13]. However, in real-world settings, a malicious sealer may
locally break the honest order of sealer rotation to occupy the leader
position and thus create profitable blocks by imitating the leader’s priority.
This attack may indirectly lead to Miner Extractable Value (MEV) issues
[14][15] and cause considerable financial loss to clients. Fortunately, Clique
mitigates this issue by adding a verification mechanism to check the identity
of each miner. However, several variants of Clique are still vulnerable to the
risk of frontrunning by malicious non-in-turn111Non-in-turn sealers contain
both edge-turn (produce secondary-priority blocks, diff=1) and out-of-turn
sealers (cannot produce blocks, diff=0) [12]. sealers and can therefore
experience a block-level frontrunning attack.

Figure 1: Operation Mechanisms of Clique and Our Attack

In this paper, we dive into Clique-based projects, to explore their improper
ways of using Clique, and identify the overlooked vulnerabilities that may
seriously threaten the consensus stability. We launch an adversarial
frontrunning attack towards its basic mechanism of sealer rotation to occupy
the leader’s position. To this end, we apply our attack to a mature in the
wild project High Performance Blockchain (HPB) [16] under an isolated
environment due to ethical principles. HPB is designed as a permissioned
blockchain applying PoA with dynamic committee to seal blocks. A sealer is
assumed to be malicious and can falsify priority parameters of difficulty
(diff for short) and delay time. The simulation results show that the
frontrunning blocks created by this malicious sealer are always accepted by
peer sealers due to its falsified diff(=2) and 0-delayed block production time
(cf. Figure 1.(b)). We then provide our intuitive but useful suggestion to its
official team. In a nutshell, the contributions are as follows.

  * -

We proposed a novel type of attack against PoA protocols, especially for
Clique-based implementations. The proposed attack can frontrun the leader’s
position by falsifying priority parameters (diff and delay time) to produce
blocks containing profitable transactions.

  * -

We investigated the assumptions and properties of Clique and dived into the
root reason that causes such attacks.

  * -

We applied our attack to a mature Clique variant (HPB) as a case study. The
results indicate that our attack strategies can cause actual damages.

  * -

We provided recommendations on how to fix the system against the proposed
attack. We further submitted the issue to its official team and obtained their
approval [17].

Paper Structure. Section II outlines the general construction of Clique.
Section III introduces the details of the frontrunning block attack. Both
experimental simulation and evaluation are presented in section IV. Section V
provides the corresponding security analysis. Countermeasures are proposed in
section VI. Finally, section VII exploits related studies, and section VIII
concludes our work.

##  II Clique Model

In this section, we introduce the Clique model by separately presenting the
threat model, underlying assumptions and the detailed algorithm.

Threat Model. Designed for permissioned blockchain systems, Clique only allows
a limited number of ($N$) sealers to participate in the consensus procedure
[5]. The network is assumed to be partially synchronized, where all messages
will be eventually delivered, but the delay time is unknown. Meanwhile, the
system requires a majority of sealers to be honest: any sealer may become
malicious and do evil activities such as dropping, delaying, duplicating, or
even faking messages, but most sealers are honest. Our attack follows the
above settings with an additional assumption: we allow an adversarial sealer
to be profitable and to obtain extra interests by frontrunning the leader
position to produce blocks. We emphasize that our attack strategy does not
break security assumptions because the assumed malicious adversary obeys all
the principles defined in the source code. Instead of consistency and liveness
[18], we target at the property of fairness [19][20] that focuses on fair
transaction ordering.

Algorithm Description. Clique allows multiple sealers to propose blocks in
parallel. Particularly, in each round, an in-turn sealer will be elected as
the leader according to the block index and the total number of sealers (cf.
line 7 Algorithm 1). The election happens in a round-robin way. Certain
sealers whose numbers follow the in-turn sealer’s become edge-turn sealers.
The amount of out-of-turn sealers is set to the smallest majority, which is
$\left\lfloor\frac{N}{2}\right\rfloor+1$. By contrast,
$\left\lceil\frac{N}{2}\right\rceil-2$ sealers following the in-turn sealer
are labeled as edge-turn sealers. In-turn sealer and edge-turn sealers compose
the largest minority. Both the in-turn sealer and edge-turn sealers are
allowed to propose blocks. Besides diff, the main difference between them is
that the edge-turn sealers (diff=1, equiv. b.weight=1, line 10) can only sign
a new block after the delay (line 12), whereas the in-turn sealer (b.weight=2,
line 8) signs and broadcasts the new block instantly (still with a short
delay). This parallel block-producing mechanism effectively prevents a single
Byzantine sealer from causing havoc on the entire network. However, forks may
occur as the system needs time to decide which block is valid. Clique solves
this issue by using a simplified version of GHOST protocol [10]: in-turn
sealers’ blocks will be granted with a higher weight to ensure that they will
be finally confirmed by a majority of sealers. In contrast, a random delay
with a wiggle (line 11) slows the block generation of an edge-turn block-
producing sealer. In this way, an in-turn sealer’s block has a better chance
of being accepted by peers than edge-turn sealers.

Algorithm 1 Block Propose and Block Verify in Clique

1:procedure Propose($sealer_{i}$) $\triangleright$ propose a block

2: while $(\mathsf{true})$ do

3: $n\leftarrow lastblock.number$

4: $delay\leftarrow block.time-now$

5: $N\leftarrow|sealers|$

6: $\textbf{wait until}\neg sign\\_recently(sealer_{i},n)$ $\triangleright$
attack

7: $\textbf{if}\,((n+1)\mod N)=i$ then

8: $\qquad weight=2$ $\triangleright$ in-turn sealing

9: else

10: $\qquad weight=1$ $\triangleright$ attack

11: $\qquad delay=rand(delay+(\frac{N}{2}+1)*500ms)$

12: $sleep(delay)$ $\triangleright$ attack

13: $block\leftarrow sign(TXs,weight)$ $\triangleright$ seal a block

14: $broadcast(block)$ $\triangleright$ send the block

15: end while

16:end procedure

17:$-----------------------------$

18:procedure Verify($sealer_{i}$) $\triangleright$ verify a block

19: $\neg sign\\_recently(sealer_{i},block.number)$

20: $\neg difficulty\\_check(sealer_{i},block.weight)$

21: $\neg inturn\\_check(sealer_{i},block.number)$

22: return $\mathsf{true}$ $\triangleright$ block is valid

23:end procedure

Verification procedure is evoked when a sealer node receives a block.
According to the original design of Clique, three core verification functions
are deployed. Block receivers first check whether the block’s proposer has
recently signed a block. Sealers maintain a local list, and reject blocks
whose proposer is labeled as recently signed. Secondly, the value of block
diff will be checked to ensure that it is restricted to $1$ or $2$. Finally,
receivers should have an additional check on blocks with a difficulty $2$, to
ensure that the proposer is a valid leader.

Figure 2: Detailed Procedures of Verification and Our Attack

##  III Frontrunning Block Attack

Recently, with the development of decentralized finance (DeFi) [21] and non-
fungible token (NFT) [22], a frontrunning attack have come to the fore. In a
blockchain system, rushing adversaries [23] may discard/replace/reorder honest
transactions for arbitrage. For instance, in the application of decentralized
exchanges, an adversary can place a transaction before others’ if the price of
an asset is going to increase [24]. This attack usually happens in the
transaction pending stage when transactions flow from the local mempool to a
block [25]. Another typical instance is sandwich attack [24]. Instead of
exploring the transaction-level attack, we focus on our block-level
frontrunning attack. Block-level means that the block should be proposed in a
proper turn. This requires their producers (sealers) to faithfully take turns
to mine blocks without breaking the prearranged turn.

As discussed, the Clique algorithm mainly uses the rotation schema to select a
leader and the priority parameters (diff and delay time) to increase
acceptance rate of the leader’s block. As an example shown in Figure 2, eight
sealers ($S_{1}$ – $S_{8}$) run the consensus algorithm. Among them, $S_{1}$
is supposed to be a malicious sealer while the other seven sealers are honest.
An ideal frontrunning block attack aims to disrupt the rotation schema and
priority parameter assignment: (i) Sealer1 can keep sealing blocks, ignoring
the rotation; (ii) Sealer1 can tamper the proposed block weight (diff) from
$1$ to $2$; (iii) or an arbitrary invalid value, e.g., 9. Such an attack is
deemed as successful if Sealer1 can seal blocks out of the legal turn among
peer blocks; meanwhile, all blocks of Sealer1 should pass the verification and
finally get accepted by honest sealers.

##  IV Attacking Implementation

This section outlines a series of attacks on commercial blockchain networks
using Clique-based consensus algorithms. Our target is to achieve an ideal
attack by disrupting the rotation schema and priority parameter assignment. As
an example of a successful attack, we depict an attacking simulation on a
widely used blockchain, HPB. Notably, we emphasize that HPB is merely one
case, and our target is to help communities to raise awareness for design
pitfalls, especially for subtle logic errors hidden in complex code.

Experiment Configuration. We establish the HPB private blockchain on a local
workstation with Centos 7 x86_64 operating system. We simulate multiple
consensus sealers by using different ports. Our private blockchain consists of
six nodes: five of them are sealer nodes ($N\in\\{0,1,...,4\\}$) responsible
for mining, and the other is a bootnode [26] for peer detection. We set the
block generation rate at five seconds, and then continuously send transactions
to any sealer at a constant rate ($10$ TXs/s) in a fixed period ($30$
minutes).

Experimental Procedure. The experiment is conducted from two sides. Firstly,
we consider a normal case where the operations of all six nodes are honest. We
compile the HPB client go-hpb [27] with official source code and refer to the
original program as $\mathsf{P_{\mathcal{O}}}$. Then, we faithfully execute
$\mathsf{P_{\mathcal{O}}}$. Five enrolled sealers are assumed to be honest and
will follow the rule of consensus honestly. The results are measured by the
output address addr of the in-turn sealer in each round of block production
(See code in Listing LABEL:lst:label). These experiments are used as a
benchmark against the experiments suffering attacks.

With the intention of keeping proposing blocks, malicious nodes need to modify
the source code of go-hpb and produce $\mathsf{P_{\mathcal{M}}}$ where local
block generation constraints (cf. line 6 Algorithm 1) are nullified, and block
diff is fixed at $2$ (line 10). On the code level, simply omitting code
related to those constraints may achieve the nullification and breaks the
rotation schema. Falsifying the difficulty assignment process by changing
diff=1 to diff=2 will set diff to a static $2$. Moreover, omitting the delay
time related code (cf. line 12) gives malicious node further priority in block
confirmation.

Therefore, secondly, we simulate the frontrunning attack, in which one
(denoted by Sealer2) of the five sealers is malicious with intentions to
frontrun the position of an in-turn sealer, while the other four sealers
(Sealer{0/1/3/4}) remain honest and execute $\mathsf{P_{\mathcal{O}}}$
faithfully. Sealer2 first modifies the source code, falsifies its diff to a
static 2 (cf. line 10 Algorithm 1) and omits its delay time (cf. line 12
Algorithm 1), so that Sealer2 has the same acceptance weight (first-priority)
as the honest in-turn sealer with even faster confirmation. The condition of
sign_recently (cf. line 6 Algorithm 1) is also omitted locally, so that
Sealer2 can produce blocks continuously even if it has signed a block
recently. Sealer2 then compiles the modified source code and executes the
returned program $\mathsf{P_{\mathcal{M}}}$. Honest sealers run
$\mathsf{P_{\mathcal{O}}}$ while malicious Sealer2 operates
$\mathsf{P_{\mathcal{M}}}$. We observe the acceptance rate of each sealer’s
blocks by outputting the block sealer’s address accompanied by the diff field
(using methods in Appendix A). If the miner address of each block turns out to
be the same, namely $addr_{2}$, Sealer2 achieves the goal of frontrunning the
original in-turn sealer and producing blocks that outpace others. In this
case, our attack is considered to be successful. Figure 2 demonstrates the
detailed procedures of verification and the attack.

Experimental Result. Figure 3 demonstrates the experimental results of both
block and transaction creation. In the first experiment, all sealers generate
$360$ blocks within $30$ minutes in total, and each of them generates $70$
blocks approximately. This indicates that these sealers generate blocks with
almost equal possibilities. Meanwhile, we observe that the transactions are
equally distributed in each block (50 TXs/block) as well. On the contrary, in
the second experiment, most of the blocks (over $300$ blocks) are generated by
Sealer2 ($\mathsf{0xa5a...}$, see the screenshots in Appendix A), and the
transactions in Sealer2’s blocks are over 15K in total. The results
demonstrate that a malicious sealer running $\mathsf{P_{\mathcal{M}}}$ can
successfully frontrun both blocks and transactions.

##  V Attacking Analysis

In this section, we dive into the root reason which makes such attacks
feasible. We then analyze the attacking impacts for the blockchain ecosystem.

Root Reason. The original Clique protocol adopted by the implementation of
Ethereum is equipped with three critical verification conditions upon block
receipt. First, the block is considered invalid if its sealer has signed a
block in recent $\left\lfloor\frac{N}{2}\right\rfloor+1$ turns, which means
that only $\left\lceil\frac{N}{2}\right\rceil-1$ can propose a block in each
round (cf. line 2 Algorithm 1). Second, the valid weight of a block is
restricted to only $1$ or $2$ (line 3). Thirdly, the validity of a block
weight needs to be verified corresponding to the sealer’s identity, that is,
whether the sealer holds a valid leader position when it penetrates a block
with a weight equal to $2$ (line 4). The main weakness of Clique applied in
our target network is its exceptional logic in difficulty validity check. By
the design, Clique applies the rotation schema to ensure that sealers take
turns to sign a block. However, without the $sign\\_recently$ check and
$inturn\\_check$ verification, a malicious sealer can easily break this logic
of block generation: the sealer can simply propose their blocks continuously
with a weight (equiv. diff) equal to $2$, and thus holds priority in block
acceptance with only little modifications to the local client. In addition,
there is a latency in the proposing procedure for honest in-turn sealers (line
6). However, a malicious sealer can also shorten the latency in order to
achieve a higher success rate.

Attacking Impact. The frontrunning block attack brings two consequences.
Firstly, it is harmful to other honest sealers. With constant attacks from
malicious sealers, the mining opportunity for honest sealers may reduce
significantly. In this case, the honest sealers may lose mining rewards that
they should have obtained. Secondly, such attacks damage the interests of
users. Since all the transactions are visible to the sealers, malicious
sealers with advanced knowledge can detect a profitable trade and replace
these users’ transactions with their own ones by performing frontrunning block
attacks. What’s worse, malicious sealers may arbitrarily drop users’
transactions, directly harming the users’ interests. The attack does not harm
the target blockchain’s consistency or liveness. However, it undermines the
fairness of block orders in practice. Notably, HPB maintains its decentralized
trading platform Hpdex [28], which can be vulnerable to the attack.

Table I compares the properties broken by different attacks, while Table II
shows the main differences among impacts of several attacks. Involving
continuous controls over block issuance, our attack may cover a relatively
wider range of victims compared to other known attacks. As sandwich attacks
are achieved by frontrunning and backrunning a pair of profitable transactions
at the same time, an evil sealer can easily commit such attacks on top of our
attacking situations.

Table I: Comparison on security properties

Attack | Assumption | Consistency | Liveness | Fairness | Note
---|---|---|---|---|---
This work | honest sealers $\textgreater\frac{N}{2}^{1}$ | ✓ | ✓ | ✗ | block-level attack against in-turn sealers
PoA attack Type-I [12] | honest sealers $\textgreater\frac{N}{2}$, attacker honest but rational2 | ✓ | ✓ | ✗ | transaction-level
PoA attack Type-II [12] | honest sealers $\textgreater\frac{N}{2}$, attacker honest but rational | ✓ | ✓ | ✗ | block-level attack against edge-turn sealers
Sandwiching3 [24] | depend on referenced consensus protocol | ✓ | ✓ | ✗ | transaction-level
Clone attack [29] | honest sealers $\textgreater\frac{N}{2}$ | ✗ | ✗ | N/A | block-level attack for double-spending
51% attack [30] | more than $50\%$ computational power controlled by a miner group | ✗ | ✗ | N/A | double-spending

  * 1

The assumption means the malicious tolerance in PoA protocols is
$t\textless\frac{N}{2}$.

  * 2

Rational: Seeking to maximize their profits within the scope of code
principles

  * 3

Sandwiching is presented as a practical instance of profitable transaction
order manipulation, rather than attacks at the consensus level.

  * 4

✗indicates the property is vulnerable under current attack, while ✓means the
opposite.

##  VI Countermeasures

The verification procedure of original Clique protocol is equipped with the
three critical conditions (cf. lines 2-4 Algorithm 2). However, the derivative
protocols may underestimate their importance. In the case of our target
blockchain network HPB, we find the logic error in conditional expressions of
the code. The error makes the system lack verification conditions related to
both sealer’s validity and the correspondence between a block’s weight and its
sealer’s identity. The countermeasure is straightforward. The code logic error
makes HPB lack two crucial verification checks, and this absence further
results in vulnerabilities of HPB protocols. Therefore, fixing the mode logic
error can directly plug the loophole. It is worth mentioning that official HPB
team has already accepted our proposal (PR report [17]). We suggest that
future projects based on Clique could cautiously and comprehensively assess
their security guarantees.

Algorithm 2 highlights the fix points to the corresponding blockchain code.
Since the clients can be compiled locally and the block proposing procedure is
conducted independently, malicious sealers can easily falsify the proposing
related code and manipulate the proposing parameters. As a consequence, the
most effective way to prevent such manipulation is to strengthen the
verification procedure, which is deployed on every sealer node, since it is
difficult to compromise most nodes at the same time. As for flawed clique-
based networks and future projects, rechecking the code logic and letting
verification functions remain effective is essential, including sign_recently,
difficulty_check and inturn_check.

Algorithm 2 Block Verify in Clique

1:procedure Verify($sealer_{i}$) $\triangleright$ verify a block

2: $\neg sign\\_recently(sealer_{i},block.number)$ $\triangleright$ fix point

3: $\neg difficulty\\_check(sealer_{i},block.weight)$

4: $\neg inturn\\_check(sealer_{i},block.number)$ $\triangleright$ fix point

5: return $\mathsf{true}$ $\triangleright$ block is valid

6:end procedure

##  VII Related Work

Figure 3: Experimental Results of Created Blocks/Transactions

In this section, we sort out the security vulnerabilities that have arisen in
PoA, including related research and various attacks proposed in the recent
decade.

Insecurity of PoA. Angelis et al. [13] presented the first clear PoA protocol
and clarified its impossibility under the CAP theorem [31]. PoA is inadequate
in achieving consistency when prioritising another two properties. Vincent et
al. [29] proposed the cloning attack to break the consistency guarantee. A
malicious sealer is granted abilities to clone itself into another instance
and isolate two equivalent branches to influence the chain selection. A
conflicting transaction, in this way, can be double-spent or discarded from
the canonical chain. Toyoda et al. [32] dived into a function-level analysis
by introducing a profiling tool pprof. They detected the targeted functions
that may decrease performance. Liu et al. [33] provided a quantitative
analysis towards PoA by using Markov Decision Process. They launched a related
attack against the VeChainThor’s [34] PoA implementation. This work differs
from the previous attacks in focusing on internal programming logic
vulnerabilities.

Fairness in PoA. Besides the essential properties of a consensus protocol,
consistency and liveness, Kelkar et al. [19] [20] identified the third
consensus property, transaction order-fairness. Since the manipulation of
transaction orders with non-public knowledge [35] may subvert the
profitability or validity of target transactions, the term fairness emphasizes
transactions should be output upon the order of receipt to ensure the network
users stay in a fair queue. Emerging MEV attacks against the blockchain
fairness like [14][36] mainly focus on PoW consensus protocols. Stathakopoulou
et al. [37] presented a hardware solution to prevent damage on fairness.
Recently, Wang et al. [12] exploited the fairness attacks on PoA protocols.
They pointed out underlying ways to manipulate transaction orders in PoA both
on transaction-level and block-level. As for the block-level attack, they
exploited the potentials of frontrunning edge-turn blocks (equiv. breaking
fairness of second-priority blocks) when the in-turn sealer fails for reasons
such as network congestion or being attacked. In contrast, our work focuses on
the attack against the in-turn sealer (breaking fairness of first-priority
blocks). We proposed an approach to compete for the block issuance right of
in-turn sealers in each round with only one single evil sealer.

Table II: Comparison among various attacks Attack | Attacker | Miner Damage | Trader Damage
---|---|---|---
This work | Miner | ✓ | ✓
PoA Type-I/II [12] | Miner | ✓ | ✓
Sandwiching [24] | Trader | ✗ | ✓
Clone attack [29] | Miner | ✗ | ✓

##  VIII Conclusion

Proof of Authority is one of the most prevailing consensus mechanisms in
state-of-the-art permissioned blockchain systems. In this paper, we first
explored the security issue of a Clique-based protocol used in the real-world
projects. Then we focused on the block-level frontrunning attack by breaking
the proper order of block issuance. We further launched the attack on HPB
private chain, simulating strategies by falsifying priority parameters and
maintaining an advantageous position during the sealer rotation. The attack
impeded consensus stability and caused monetary loss for both normal users and
honest sealers. Results from our experiments proved the effectiveness of our
frontrunning attack. Moreover, we provided our recommendations and disclosed
the report to the official HPB team (cf. [17]). We hope that other Clique
variants can draw upon this knowledge and avoid similar design mistakes.

## Acknowledgement

Xinrui Zhang, Rujia Li and Qi Wang are partially supported by the Shenzhen
Fundamental Research Programs under Grant No.20200925154814002. Lastly, we
thank the HPB development team, especially for their open and helpful
discussion.

## References

  * [1] G. Wood, “Poa private chains,” https://github.com/ethereum/guide/blob/master/poa.md, Nov. 2015, accessed: Dec., 2021.
  * [2] P. Szilágyi, “Eip-225: Clique proof of authority consensus protocol,” 2017, ethereum Improvement Proposals, accessed: Dec.,2021. [Online]. Available: https://eips.ethereum.org/EIPS/eip-225
  * [3] T. go-ethereum Authors, “Go ethereum,” https://github.com/ethereum/go-ethereum, Mar. 2022, accessed: Apr., 2022\.
  * [4] A. Ordian, “pairty-ethereum,” https://github.com/openethereum/parity-ethereum, Feb. 2020, accessed: Dec., 2021.
  * [5] C. N. Samuel, S. Glock, F. Verdier, and P. Guitton-Ouhamou, “Choice of ethereum clients for private blockchain: Assessment from proof of authority perspective,” in _Proceedings of the 2021 IEEE International Conference on Blockchain and Cryptocurrency (ICBC)_. IEEE, 2021, pp. 1–5.
  * [6] “Gochain,” https://gochain.io/, 2021, accessed: Dec., 2021.
  * [7] “Posa in binance smart chain,” https://github.com/binance-chain/whitepaper/blob/master/WHITEPAPER.md, 2021, accessed: Dec., 2021.
  * [8] Parity Technologies (UK) Ltd, “Poa network,” https://github.com/poanetwork/openethereum, 2021, accessed: Dec., 2021.
  * [9] “Consensys quorum,” https://github.com/ConsenSys/quorum/blob/master/consensus/clique/clique.go, 2021, accessed: Dec., 2021.
  * [10] G. Wood, “Ethereum: A secure decentralised generalised transaction ledger,” https://ethereum.github.io/yellowpaper/paper.pdf, Apr. 2022, accessed: Apr., 2022.
  * [11] Y. Sompolinsky and A. Zohar, “Secure high-rate transaction processing in bitcoin,” in _Proceedings of the 2015 International Conference on Financial Cryptography and Data Security (FC)_. Springer, 2015, pp. 507–527.
  * [12] Q. Wang, R. Li, Q. Wang, S. Chen, and Y. Xiang, “Exploring unfairness on proof of authority: Order manipulation attacks and remedies,” in _Proceedings of the 17th ACM ASIA Conference on Computer and Communications Security (ASIACCS)_. ACM, 2022.
  * [13] S. De Angelis, L. Aniello, R. Baldoni, F. Lombardi, A. Margheri, and V. Sassone, “PBFT vs proof-of-authority: Applying the CAP theorem to permissioned blockchain,” in _Proceedings of the 2018 Italian Conference on Cybersecurity (ITASEC)_ , 2018, pp. 1–11.
  * [14] P. Daian, S. Goldfeder, T. Kell, Y. Li, I. Bentov, L. Breidenbach, and A. Juels, “Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability,” in _Proceedings of the 2020 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2020, pp. 910–927.
  * [15] C. F. Torres, R. Camino _et al._ , “Frontrunner jones and the raiders of the dark forest: An empirical study of frontrunning on the ethereum blockchain,” in _30th USENIX Security Symposium (USENIX Security 21)_ , 2021, pp. 1343–1359.
  * [16] The go-hpb Authors, “High performance blockchain (hpb) – consensus,” https://github.com/hpb-project/go-hpb/tree/master/consensus, Oct. 2021, accessed: Dec., 2021.
  * [17] “go-hpb pull request,” https://github.com/hpb-project/go-hpb/tree/fixdiffbug, accessed: Dec., 2021\.
  * [18] J. Garay, A. Kiayias, and N. Leonardos, “The bitcoin backbone protocol: Analysis and applications,” in _Annual International Conference on the Theory and Applications of Cryptographic Techniques (CRYPTO)_. Springer, 2015, pp. 281–310.
  * [19] M. Kelkar, F. Zhang, S. Goldfeder, and A. Juels, “Order-fairness for byzantine consensus,” in _Proceedings of the Annual International Cryptology Conference (CRYPTO)_. Springer, 2020, pp. 451–480.
  * [20] M. Kelkar, S. Deb _et al._ , “Order-fair consensus in the permissionless setting,” _Cryptology ePrint Archive_ , vol. 2021, p. 139, 2021.
  * [21] D. A. Zetzsche, D. W. Arner, and R. P. Buckley, “Decentralized finance,” _Journal of Financial Regulation_ , vol. 6, no. 2, pp. 172–203, 2020.
  * [22] Q. Wang, R. Li, Q. Wang, and S. Chen, “Non-fungible token (nft): Overview, evaluation, opportunities and challenges,” 2021, arXiv preprint. [Online]. Available: https://arxiv.org/abs/2101.05511
  * [23] A. Kosba, A. Miller, E. Shi, Z. Wen, and C. Papamanthou, “Hawk: The blockchain model of cryptography and privacy-preserving smart contracts,” in _Proceedings of the 2016 IEEE symposium on security and privacy (SP)_. IEEE, 2016, pp. 839–858.
  * [24] L. Zhou, K. Qin, C. F. Torres, D. V. Le, and A. Gervais, “High-frequency trading on decentralized on-chain exchanges,” in _Proceedings of the 2021 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2021, pp. 428–445.
  * [25] S. Eskandari, S. Moosavi, and J. Clark, “Sok: Transparent dishonesty: front-running attacks on blockchain,” in _Proceedings of the 2019 International Conference on Financial Cryptography (FC)_. FC, 2019, pp. 170–189.
  * [26] Go Ethereum Team, “Private network tutorial,” https://geth.ethereum.org/docs/getting-started/private-net, 2021, accessed: Dec., 2021.
  * [27] The go-hpb Authors, “High performance blockchain (hpb) – chain generation,” https://github.com/hpb-project/go-hpb/blob/master/consensus/prometheus/chain_generation.go, Aug. 2021, accessed: Dec., 2021.
  * [28] H. team, “Hpdex,” https://app.hpdex.org/#/swap, accessed: Apr., 2022.
  * [29] E. Parinya, G. Vincent, and J. Guillaume, “The attack of the clones against proof-of-authority,” in _Proceedings of the 27th Annual Network and Distributed System Security Symposium (NDSS)_ , 2020.
  * [30] M. D. C. Initiative, “51% attacks,” https://dci.mit.edu/51-attacks, accessed: Apr., 2022.
  * [31] S. Gilbert and N. Lynch, “Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services,” _Acm Sigact News_ , vol. 33, no. 2, pp. 51–59, 2002.
  * [32] K. Toyoda, K. Machi, Y. Ohtake, and A. N. Zhang, “Function-level bottleneck analysis of private proof-of-authority ethereum blockchain,” _IEEE Access_ , vol. 8, pp. 141 611–141 621, 2020.
  * [33] X. Liu _et al._ , “Mdp-based quantitative analysis framework for proof of authority,” in _Proceedings of the 2019 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC)_. IEEE, 2019, pp. 227–236.
  * [34] VeChain Foundation, “Vechain docs — proof of authority,” Oct. 2021, vechain Docs, accessed: Dec., 2021. [Online]. Available: https://docs.vechain.org/thor/learn/proof-of-authority.html
  * [35] J. W. Markham, “Front-running-insider trading under the commodity exchange act,” _Cath. UL Rev._ , vol. 38, p. 69, 1988.
  * [36] K. Qin, L. Zhou, and A. Gervais, “Quantifying blockchain extractable value: How dark is the forest?” _IEEE Symposium on Security and Privacy (SP)_ , 2022\.
  * [37] C. Stathakopoulou, S. Rüsch, M. Brandenburger, and M. Vukolić, “Adding fairness to order: Preventing front-running attacks in bft protocols using tees,” in _2021 40th International Symposium on Reliable Distributed Systems (SRDS)_. IEEE, 2021, pp. 34–45.
  * [38] “Coinmarketcap,” https://coinmarketcap.com/, 2021, accessed: Dec., 2021\.

## Appendix A

Figure 4 shows a comparison between a normal case and an attacking case of
running HPB instances. The first column on the left marks the serial number of
each block. The middle column shows the addresses of in-turn sealers who have
created current blocks. The right column represents the block weights (equiv.
diff). Figure 4(a) depicts a normal case of a rotation cycle. We can observe
that the blocks are signed by five different sealers in turns. The first five
addresses ($addr_{2}$ – $addr_{5},addr_{1}$, sequentially) are not repeated
while the sixth address ($addr_{2}$) rotates to the first one, corresponding
to the rotation schema. In contrast, Figure 4(b) shows an attacking case.
Apparently, the addresses of nine consecutive blocks stay the same, indicating
that a malicious sealer has successfully skipped the procedure of sealer
rotation and sat in the leader position in most rounds. This out-of-turn
sealer frontruns others to make profits by continuously producing profitable
blocks by maintaining block weights (diff) equal to 2.

(a) Normal Case

(b) Attacking Case

Figure 4: Screenshots of Experimental Results

We use the script (cf. Listing LABEL:lst:label) to collect the above data. The
output presents the block number, miner’s address and block difficulty,
sequentially.

⬇

1#!/bin/bash

2a=$1

3for i in {0..199}

4do

5i=‘expr $i + $a ‘

6miner=‘./ghpb attach rpc_addr <<EOM

7eth.getBlock($i).miner

8EOM

9‘

10difficulty=‘./ghpb attach rpc_addr <<EOM

11eth.getBlock($i).difficulty

12EOM

13‘

14echo $i ${miner:0-46:42} ${difficulty:0-4:2}

15done

## Appendix B. Notations

We highlight several featured notations in the following Table III to clarify
their usages in this work.

Table III: Featured Notations

Symbol |  Item | Functionalities
---|---|---
diff | Difficulty | the difficulty (weight value) of a block
delay time | Delay time | the delay time of current block issuance
$N$ | Committee size | the total number of sealers
$\mathsf{P_{\mathcal{O}}}$ | Original client | the normal (intact) client program of go-hpb
$\mathsf{P_{\mathcal{M}}}$ | Malicious client | the tampered client program of go-hpb
$S_{\star}$ | Sealer | refer to a sealer by index
$go$-$hpb$ | HPB client | the client program of HPB project
$addr_{\star}$ | Sealer address | the address of a sealer

## Appendix C

Table.IV lists several mainstream commercial blockchain projects adopting
Clique-based consensus algorithms. We present their market values collecting
from public information (CoinMarketCap [38]). The data demonstrate that
Clique-related projects occupy a considerable market share, which emphasizes
the importance of its protocol security.

Table IV: Clique-based Projects

Project | Client | Market Cap
---|---|---
Go-Ethereum | Clique | $343,061,278,394
Binance-chain | Clique-variant | $17,426,222,620
Polygon (MATIC) | Clique-forked | $9,866,753,531
Openethereum | Clique-forked | $343,061,278,394
PoA network | Clique-variant | $23,723,240
HPB (This work) | Clique-variant | $3,058,901
Ethereum Classic | Clique-forked | $4,161,701,776
ConsenSys | Clique-forked | -
GoChain | Clique-forked | $24,702,737
Daisy | Clique-forked | -
Olecoin | Clique-forked | -
EEX | Clique-forked | -
AplaProject | Clique-forked | -
Tomochain | Clique-forked | $114,756,610

  * 1

The variant means a project makes modifications, while forked means directly
uses the source code from Clique.

  * 2

Data accessed in April, 2022.