# Rank and Select on Degenerate Strings

Philip Bille111Supported by Danish Research Council grant DFF-8021-002498.,
Inge Li Gørtz11footnotemark: 1, and Tord Stordalen
DTU Compute, Technical University of Denmark Lyngby, Denmark {phbi, inge,
<EMAIL_ADDRESS>
###### Abstract

A _degenerate string_ is a sequence of subsets of some alphabet; it represents
any string obtainable by selecting one character from each set from left to
right. Recently, Alanko et al. generalized the rank-select problem to
degenerate strings, where given a character _c_ and position _i_ the goal is
to find either the _i_ th set containing _c_ or the number of occurrences of
_c_ in the first _i_ sets [SEA 2023]. The problem has applications to
pangenomics; in another work by Alanko et al. they use it as the basis for a
compact representation of _de Bruijn Graphs_ that supports fast membership
queries.

In this paper we revisit the rank-select problem on degenerate strings,
introducing a new, natural parameter and reanalyzing existing reductions to
rank-select on regular strings. Plugging in standard data structures, the time
bounds for queries are improved exponentially while essentially matching, or
improving, the space bounds. Furthermore, we provide a lower bound on space
that shows that the reductions lead to succinct data structures in a wide
range of cases. Finally, we provide implementations; our most compact
structure matches the space of the most compact structure of Alanko et al.
while answering queries twice as fast. We also provide an implementation using
modern vector processing features; it uses less than one percent more space
than the most compact structure of Alanko et al. while supporting queries four
to seven times faster, and has competitive query time with all the remaining
structures.

##  1 Introduction

Given a string $S$ over an alphabet $[1,\sigma]$ the _rank-select problem_ is
to preprocess $S$ to support, for any $c\in[1,\sigma]$,

  * •

$\textsf{rank}_{S}(i,c)$: return the number of occurrences of $c$ in $S[1,i]$

  * •

$\textsf{select}_{S}(i,c)$: return the index $j$ of the $i$th occurrence of
$c$ in $S$

This fundamental string problem has been studied extensively due to its wide
applicability, see, e.g., [8, 26, 14, 28, 27, 7, 23, 11, 6, 5, 25, 18, 24,
17], references therein, and surveys [12].

A _degenerate string_ is a sequence $X=X_{1},\ldots X_{n}$ where each $X_{i}$
is a subset of $[1,\sigma]$. We define its _length_ to be $n$, its _size_ to
be $N=\sum_{i}|X_{i}|$, and denote by $n_{0}$ the number of empty sets among
$X_{1},\ldots,X_{n}$. Degenerate strings have been studied since the 80s [1]
and the literature contains papers on problems such as degenerate string
comparison [4], finding string covers for degenerate strings[10], and pattern
matching with degenerate patterns, degenerate texts, or both [1, 19].

Alanko, Biagi, Puglisi, and Vuohtoniemi [2] recently generalized the rank-
select problem to the _subset rank-select problem_ , where the goal is to
preprocess a given degenerate string $X$ to support

  * •

$\textsf{subset-rank}_{X}(i,c)$: return the number of sets in
$X_{1},\ldots,X_{i}$ that contain $c$

  * •

$\textsf{subset-select}_{X}(i,c)$: return the index of the $i$th set that
contains $c$

Their motivation for studying this problem is to support fast membership
queries on _de Bruijn graphs_ , a useful tool in pangenomic problems such as
genome assembly and pangenomic read alignment (see [2, 3] for details and
further references). Specifically, in another work by some of the authors [3],
they show how to represent the de Bruijn graph of all length-$k$ substrings of
a given string such that membership queries on the graph can be answered using
$2k$ subset-rank queries. They also provide an implementation that, when
compared to the previous state of the art, improves query time by one order of
magnitude while improving space usage, or by two orders of magnitude with
similar space usage.

Their result for subset rank-select is the following [2]. They introduce the
_Subset Wavelet Tree_ , a generalization of the well-known wavelet tree (see
[16]) to degenerate strings. It supports both subset-rank and subset-select
queries in $O(\log\sigma)$ time and uses $2(\sigma-1)n+o(n\sigma)$ bits of
space in the general case. In the special case of $n=N$ (which is the case for
their representation of de Bruijn Graphs in [3]) they show that their
structure uses $2n\log\sigma+o(n\log\sigma)$ bits. We note that their analysis
for this special case happens to generalize nicely to also show that their
structure uses at most $2N\log\sigma+2n_{0}+o(N\log\sigma+n_{0})$ bits for any
$N$.

Furthermore, in [3], Alanko, Puglisi, and Vuohtoniemi present a number of
reductions from the subset rank-select to the regular rank-select problem. We
will elaborate on these reductions later in the paper.

##  2 Our Results

Our contributions are threefold. Firstly, we introduce the natural parameter
$N$ and revisit the subset rank-select problem to reanalyze a number of simple
and elegant reductions to the regular rank-select problem, based on the
reductions from [3]. We express the complexities in terms of the performance
of a given rank-select structure, achieving flexible bounds that benefit from
the rich literature on the rank-select problem (Theorem 1). Secondly, we show
that any structure supporting either subset-rank or subset-select must use at
least $N\log\sigma-o(N\log\sigma)$ bits in the worst case (Theorem 2). By
plugging a standard rank-select data structure into Theorem 1 we, in many
cases, match this bound to within lower order terms, while simultaneously
matching the query time of the fastest known rank-select data structures (see
below). Note that any lower bound for rank-select queries also holds for
subset rank-select queries since any string is also a degenerate string. All
our results hold on a word RAM with logarithmic word-size. Finally, we provide
implementations of the reductions and compare them to the implementations of
the Subset Wavelet Tree provided in [2], and the implementations of the
reductions provided in [3]. Our most compact structure matches the space of
their most compact structure while answering queries twice as fast. We also
provide a structure using vector processing features that matches the space of
the most compact structure while imporving query time by a factor four to
seven, remaining competitive with the fast structures for queries.

We now elaborate on the points above. The reductions are as follows.

######  Theorem 1.

Let $X$ be a degenerate string of length $n$, size $N$, and with $n_{0}$ empty
sets over an alphabet $[1,\sigma]$. Let $\mathcal{D}$ be a
$\mathcal{D}_{b}(\ell,\sigma)$-bit data structure for a length-$\ell$ string
over $[1,\sigma]$ that supports rank in $\mathcal{D}_{r}(\ell,\sigma)$ time
and select in $\mathcal{D}_{s}(\ell,\sigma)$ time. If $n_{0}=0$ we can solve
subset rank-select on $X$ in
(i) $\mathcal{D}_{b}(N,\sigma)+N+o(N)$ bits, $\mathcal{D}_{r}(N,\sigma)+O(1)$
subset-rank-time, and $\mathcal{D}_{s}(N,\sigma)+O(1)$ subset-select-time.
Otherwise, if $n_{0}>0$ we can solve subset rank-select on $X$ in
(ii) the bounds in (i) where we replace $N$ by $N^{\prime}=N+n_{0}$ and
$\sigma$ by $\sigma^{\prime}=\sigma+1$.
(iii) the bounds in (i) with additional $\mathcal{B}_{b}(n,n_{0})$ bits of
space, additional $\mathcal{B}_{r}(n,n_{0})$ time for subset-rank, and
additional $\mathcal{B}_{s}(n,n_{0})$ time for subset-select. Here
$\mathcal{B}$ is a data structure on a length-$n$ bitstring that contains
$n_{0}$ 1s, uses $\mathcal{B}_{b}(n,n_{0})$ bits, and supports
$\textsf{rank}{}(\cdot,\texttt{1})$ in $\mathcal{B}_{r}(n,n_{0})$ time and
$\textsf{select}{}(\cdot,\texttt{0})$ in $\mathcal{B}_{s}(n,n_{0})$ time.

Here Theorem 1(i) and (ii) are based on the reduction from [3, Sec. 4.3], and
Theorem 1(iii) is a variation of Theorem 1(ii) that handles empty sets using a
natural, alternative strategy. By plugging a standard rank-select structure
into Theorem 1 we exponentially improve query times while essentially
matching, or improving, space usage compared to Alanko et al. [2]. For
example, consider the rank-select structure by Golynski, Munro, and Rao [14]
which uses $\ell\log\sigma+o(\ell\log\sigma)$ bits, supports rank in
$O(\log\log\sigma)$ time, and supports select in constant time. These query
times are optimal in succinct space, see e.g. [8].

For $n_{0}=0$, plugging this structure into Theorem 1(i) yields an
$N\log\sigma+N+o(N\log\sigma+N)$ bit data structure supporting subset-rank in
$O(\log\log\sigma)$ time and subset-select in constant time. Compared to the
previous result by Alanko et al. [2], this improves the constant on the space
bound from $2$ to $1+1/\log\sigma$ and improves the query time from
$O(\log\sigma)$ for both queries to $O(\log\log\sigma)$ for subset-rank and
constant for subset-select. Note that the additional $N$ bits in the space
bound are a lower order term when $\sigma=\omega(1)$.

For $n_{0}>0$, plugging their structure into Theorem 1(ii) gives the same time
bounds as above and the space bound

$(N+n_{0})\log(\sigma+1)+(N+n_{0})+o(n_{0}\log\sigma+N\log\sigma+N+n_{0})$

bits. If $n_{0}=o(N)$ and $\sigma=\omega(1)$, the space bound is identical to
the one above. In any case, the query time is still improved exponentially.

Alternatively, by plugging it into Theorem 1(iii) the space bound becomes
$N\log\sigma+o(N\log\sigma)$ \+ $\mathcal{B}_{s}(n,n_{0})$ bits. For
$n=o(N\log\sigma)$ we can choose $\mathcal{B}$ to be an $(n+o(n))$-bit data
structure with constant time rank and select, such as [9, 20], again achieving
the same space and time bounds as when $n_{0}=0$. Otherwise, we can plug in
any data structure for $\mathcal{B}$ that is sensitive to the number of
$1$-bits in the bitvector. For example, if $n_{0}=O(\log n)$ we can store the
positions of the $1$-bits in sorted order using $O(n_{0}\log n)=O(\log^{2}n)$
bits, supporting $\textsf{select}{}(i,\texttt{1})$ in constant time and
$\textsf{rank}{}(i,\cdot)$ in $O(\log n_{0})=O(\log\log n)$ time using binary
search. We can also binary search for $\textsf{select}{}(i,\texttt{0})$ in
$O(\log n_{0})=O(\log\log n)$ time using the fact that — if the $i$th position
of a $1$-bit is $p_{i}$ — there are $p_{i}-i$ zeroes in the prefix ending at
$p_{i}$. There are many such sensitive data structures that obtain various
time-space trade-offs, e.g [26, 15].

We also show the following lower bound on the space required to support either
subset-rank or subset-select on a degenerate string.

######  Theorem 2.

Let $X$ be a degenerate string of size $N$ over an alphabet $[1,\sigma]$. Any
data structure supporting subset-rank or subset-select on $X$ must use at
least $N\log\sigma-o(N\log\sigma)$ bits in the worst case.

Thus, applying Theorem 1 in many cases results in succinct data structures,
whose space deviates from this lower bound by at most a lower order term. The
three examples above each illustrate this when respectively (1)
$\sigma=\omega(1)$, (2) $n_{0}=o(N)$ and $\sigma=\omega(1)$, and (3)
$n=o(N\log\sigma)$.

Finally, we provide implementations and compare them to variants of the Subset
Wavelet Tree [2] and the reductions [3] implemented by Alanko et al.
Specifically, we apply the test framework from [2] and run two types of tests:
one where the subset rank-select structures are used to support $k$-mer
queries on a de Bruijn Graph (the motivation for, and practical application
of, the subset rank-select problem), and one where subset-rank queries are
tested in isolation. We implement Theorem 1(iii) and plug in efficient off-
the-shelf rank-select structures from the _Succinct Data Structure Library
(SDSL)_ 222https://github.com/simongog/sdsl-lite [13]. We also implement a
variation of another reduction from [3, Sec. 4.2], which is more optimized for
genomic test data. The highlight is our most compact structure, which matches
the space of their most compact structure while supporting queries twice as
fast, as well as our structure using vector processing, which matches the most
compact structure while supporting queries four to seven times faster.

##  3 Reductions

We now present the reductions from Theorem 1. Let $X$, $\mathcal{D}$, and
$\mathcal{B}$ be defined as in Theorem 1. Furthermore, let $\mathcal{V}$ be
the data structure from [20], which for a length-$\ell$ bitstring uses
$\ell+o(\ell)$ bits and supports rank and select in constant time.

###  3.1 Reductions (i) and (ii)

First assume that $n_{0}=0$. For each $X_{i}$ let the string $S_{i}$ be the
concatenation of the characters in $X_{i}$ in an arbitrary order, and let the
string $R_{i}$ be a single 1 followed by $|X_{i}|-1$ 0s. This is always
possible since $|X_{i}|\geq 1$. Let $S$ (resp. $R$) be the concatenation of
$S_{1},\ldots,S_{n}$ (resp. $R_{1},\ldots,R_{n})$ in that order, with an
additional 1 appended after $R_{n}$. The lengths of $S$ and $R$ are
respectively $N$ and $N+1$. See Figure 1 for an example. The data structure
consists of $\mathcal{D}$ built over $S$ and $\mathcal{V}$ built over $R$,
which takes $\mathcal{D}(N,\sigma)+N+o(N)$ bits.

To support $\textsf{subset-rank}{}(i,c)$, compute the starting position
$k=\textsf{select}{}_{R}(i+1,\texttt{1})$ of $S_{i+1}$ and return
$\textsf{rank}{}_{S}(k-1,c)$. To support $\textsf{subset-select}{}(i,c)$, find
the index $k=\textsf{select}{}_{S}(i,c)$ of the $i$th occurrence of $c$, and
return $\textsf{rank}{}_{R}(k,\texttt{1})$ to determine which set $k$ is in.
Since rank and select queries on $R$ take constant time, subset-rank and
subset-select queries take respectively $\mathcal{D}_{r}(N,\sigma)+O(1)$ and
$\mathcal{D}_{s}(N,\sigma)+O(1)$ time, achieving the bounds stated in Theorem
1(i).

If $n_{0}\neq 0$, add a new character $\sigma+1$ and replace each empty set
with the singleton set $\\{\sigma+1\\}$, and then apply reduction (i). This
instance has $N^{\prime}=N+n_{0}$ and $\sigma^{\prime}=\sigma+1$, achieving
the bounds in Theorem 1(ii).

###  3.2 Reduction (iii)

Let $E$ denote the length-$n$ bitvector where $E[i]=1$ if $X_{i}=\emptyset$
and $E[i]=0$ otherwise. Let $X^{\prime\prime}$ denote the degenerate string
obtained by removing all the empty sets from $X$. The data structure consists
of reduction (i) over $X^{\prime\prime}$ and $\mathcal{B}$ built over $E$.
This takes $\mathcal{D}_{b}(N,\sigma)+N+o(N)+\mathcal{B}_{b}(n,n_{0})$ bits.
To support $\textsf{subset-rank}{}_{X}(i,c)$ first compute
$k=i-\textsf{rank}{}_{E}(i,\texttt{1})$, mapping $X_{i}$ to its corresponding
set $X^{\prime\prime}_{k}$. Then return $\textsf{subset-
rank}{}_{X^{\prime\prime}}(k,c)$. This takes
$\mathcal{B}_{r}(n,n_{0})+\mathcal{D}_{r}(N,\sigma)+O(1)$ time. To support
$\textsf{subset-select}{}_{X}{}(i,c)$, find $k=\textsf{subset-
select}{}_{X^{\prime\prime}}(i,c)$ and return
$\textsf{select}{}_{E}(k,\texttt{0})$, the position of the $k$th zero in $E$
(i.e., the $k$th non-empty set). This takes
$\mathcal{B}_{s}(n,n_{0})+\mathcal{D}_{s}(N,\sigma)+O(1)$, matching the stated
bounds.

$X=$ | $\Bigg{\\{}\,\begin{matrix}\texttt{A}\\\ \texttt{C}\\\ \texttt{G}\end{matrix}\,\Bigg{\\}}$ | $\Bigg{\\{}\,\begin{matrix}\texttt{A}\\\ \texttt{T}\end{matrix}\,\Bigg{\\}}$ | $\Bigg{\\{}\,\begin{matrix}\texttt{C}\end{matrix}\,\Bigg{\\}}$ | $\Bigg{\\{}\,\begin{matrix}\texttt{T}\\\ \texttt{G}\end{matrix}\,\Bigg{\\}}$
---|---|---|---|---
| $X_{1}$ | $X_{2}$ | $X_{3}$ | $X_{4}$

$S=$ | ACG | AT | C | TG |
---|---|---|---|---|---
$R=$ | 100 | 10 | 1 | 10 | 1
| $S_{1}$ | $S_{2}$ | $S_{3}$ | $S_{4}$ |

Figure 1: _Left:_ A degenerate string $X$ over the alphabet
$\\{\texttt{A},\texttt{C},\texttt{G},\texttt{T}\\}$ where $n=4$ and $N=8$.
_Right:_ The reduction from Theorem 1(i) on $X$. White space is for
illustration purposes only. To compute $\textsf{subset-rank}{}(2,\texttt{A})$,
we first compute $\textsf{select}{}_{R}(3,\texttt{1})=6$. Now we know that
$S_{2}$ ends at position $5$, so we return
$\textsf{rank}{}_{S}(5,\texttt{A})=2$. To compute $\textsf{subset-
select}{}(2,\texttt{G})$ we compute $\textsf{select}{}_{S}(2,\texttt{G})=8$,
and compute $\textsf{rank}{}_{R}(8,\texttt{1})=4$ to determine that position 8
corresponds to $X_{4}$.

##  4 Lower Bound

In this section we prove Theorem 2. The strategy is as follows. Any structure
supporting subset-rank or subset-select on $X$ is a representation of $X$
since we can fully recover $X$ by repeatedly using either of these operations.
We will lower bound the number $L$ of distinct degenerate strings that can
exist for a given $N$ and $\sigma$. Any representation of $X$ must be able to
distinguish between these instances, so it needs to use at least $\log_{2}L$
bits in the worst case. Let sufficiently large $N$ and $\sigma=\omega(\log N)$
be given and assume without loss of generality that $\log N$ and $N/\log N$
are integers. Consider the class of degenerate strings $X_{1},\ldots,X_{n}$
where each $|X_{i}|=\log N$ and $n=N/\log N$. There are $\binom{\sigma}{\log
N}^{N/\log N}$ such degenerate strings, so any representation must use at
least

$\displaystyle\log\binom{\sigma}{\log N}^{N/\log N}$
$\displaystyle=\frac{N}{\log N}\log\binom{\sigma}{\log N}$
$\displaystyle\geq\frac{N}{\log N}\log\left(\frac{\sigma-\log N}{\log
N}\right)^{\log N}$ $\displaystyle=N\log\left(\frac{\sigma-\log N}{\log
N}\right)$ $\displaystyle=N\log\sigma-o(N\log\sigma)$

bits, concluding the proof.

##  5 Experimental Setup

###  5.1 Setup and Data

The code to replicate our results is available on
GitHub333https://github.com/tstordalen/subset-rank-select. Our tests are based
on the test framework by Alanko et al. [2], also available on
GitHub444https://github.com/jnalanko/SubsetWT-Experiments/. Like them, we used
the following data sets.

  1. 1.

A pangenome of $3682$ E. coli genomes, available on
Zenodo555https://zenodo.org/record/6577997. According to [2], the data was
collected by downloading a set of 3682 E. Coli assemblies from the National
Center for Biotechnology Information.

  2. 2.

A human metagenome (SRA identifier ERR$5035349$) consisting of a set of
$\approx 17$ million length-$502$ sequence reads sampled from the human gut
from a study on irritable bowel syndrome and bile acid malabsorption [21].

We applied two tests. Firstly, we plugged our data structures into the $k$-mer
query test from [2]; they plug subset rank-select structures into their
$k$-mer index and query a large number of $k$-mers. Secondly, we tested the
subset rank-select structures in isolation by building the $k$-mer indices,
extracting the subset rank-select structures, and performing twenty million
randomly generated subset-rank queries. For each measurement we built only the
structure under testing, and timed only the execution of the queries. Each
value reported below is the average of five such measurements. Note that, like
[2], we do not test subset-select queries; only subset-rank queries are
necessary for their $k$-mer index.

All the tests were run on a system with a $3.00$GHz i7-1185G7 processor and
$32$ gigabytes of DDR4 random access memory, running Ubuntu $22.04.3$ LTS with
kernel version 6.2.0-35-generic. The programs were compiled using g++ version
11.4.0 with compiler flags -O3, -march=native, and -DNDEBUG.

###  5.2 Data Structures

This section summarizes a representative subset of the data structures we
tested; see appendix B for a description of, and results for, the remaining
data structures. We implement both Theorem 1(iii) as well as variation of the
reduction _split representation_ from [3, Sec 4.2]; this reduction is
optimized for their $k$-mer query structure built over genomic data, in which
most of the sets are singletons. We name our variation the _dense-sparse
decomposition (DSD)_ , which works as follows. The empty sets are handled in
the same way as in Theorem 1(iii). Furthermore, we store a sparse bitvector of
length $n$ for each character, i.e., A, C, G, and T. For each $X_{i}$ of size
at least two we remove $|X_{i}|-1$ of the characters and set the $i$th bit in
the corresponding bitvector to $1$. What remains are $n-n_{0}$ singleton sets,
i.e., a regular string, for which we store a rank-select structure. A query
thus consists of three rank queries; one to eliminate empty sets, one in the
regular string, and one in the sparse bitvector. In the split representation
by [3], each such set is instead removed and _all_ the characters are
represented in the additional bitvectors.

The data structures we tested are as follows. Matrix is the benchmark
structure from [2], consisting of one bitvector per character (i.e., a
$4\times n$ matrix). Thm 1(iii) is the reduction from Theorem 1(iii), using a
wavelet tree for the string, a bitvector for the length-$N$ indicator string,
and a sparse bitvector for the empty sets. DSD (x), SWT (x), and Split (x) are
the DSD, Subset Wavelet Tree, and split representation parameterized by x,
respectively, where x may be any of the following data structures: _(1)_ scan,
the structure from Alanko et al. [2, Sec. 5.2], inspired by scanning
techniques for fast rank queries on bitvectors, _(2)_ split, a rank structure
for size-four alphabets optimized for the skewed distribution of singleton to
non-singleton sets [2, Sec 5.3] (not to be confused with the split
representation) _(3)_ rrr, an SDSL wavelet tree using $H_{0}$-compressed
bitvectors, based mainly on the result by Raman, Raman, and Rao Satti [28],
_(4)_ rrr gen., a generalization of RRR to size-four alphabets [2, Sec. 5.4],
_(5)_ ef, an efficient implementation of rank queries on a bitvector stored
using Elias-Fano encoding from [22], and _(6)_ plain, a standard SDSL
bitvectors supporting rank in constant time.

Furthermore, [3] implements Concat (rrr), which is essentially reduction (ii)
using a wavelet tree with RRR-compressed bitvectors, and we also implement the
structure DSD (SIMD). It is based on a standard idea for compact data
structures; we divide the string into blocks, precompute the answer to rank
queries up to each block, and compute partial rank queries for blocks as
needed using word parallelism (this is also an essential idea in the ‘scan’
structure by [2]). We use _SIMD (single instruction, multiple data)_
instructions to speed up the partial in-block rank queries, which allows for
large blocks and a reduction in space (see Appendix B). Most computers support
SIMD to some extent, allowing the same operation to be performed on many words
simultaneously. We used AVX512, which supports $512$-bit vector registers.

Figure 2: Note that the $x$-axis is truncated in both plots. The two gray
lines represent the performance of the benchmark solution “Matrix”. The
crosses indicate our data structures and the circles indicate the data
structures from [2, 3]. _Left:_ Results of the $k$-mer query test on the
metagenome data set. _Right:_ The result of the subset-rank test on the
metagenome data set. The space is in number of bits per symbol, i.e.,
$\text{bits}/N$.

##  6 Results

The test results for the metagenome data set can be seen in Figure 2; the
results for the E. Coli data set are similar. See appendix A for the data
belonging to Figure 2, and appendix B for the results of the data structures
omitted from this figure. The fastest structure is SWT (scan), but it is large
and is outperformed by the benchmark solution on both parameters. Our
unoptimized reduction Thm1(iii) uses $20-60\%$ more space than the remaining
structures of [2, 3] while remaining within a factor two in query time of most
of them. Our fastest structure, DSD (scan), is competitive with both Split
(ef) and Split (rrr). Our most compact structure DSD (rrr) matches the space
of the previous smallest structure, Concat (ef), while supporting queries
twice as fast. Our SIMD-enhanced structure uses less than one percent more
space than Concat (ef) while supporting queries four to seven times faster. It
is also competitive with the fast and compact structures Split (ef) and Split
(rrr). We note that the entropies for the distributions of sets in the
Metagenome and E. Coli data sets are respectively $2.21$ and $2.24$ bits (as
seen in [2]), and that reduction from $2.44$ bits (Split (rrr), Metagenome) to
$2.28$ bits (SIMD, Metagenome) reduces the distance to the entropy from
approximately $10\%$ to $3\%$, while simultaneously supporting queries faster.

## References

  * [1] Karl R. Abrahamson.  Generalized string matching.  SIAM J. Comput., 16(6):1039–1051, 1987.  doi:10.1137/0216067.
  * [2] Jarno N. Alanko, Elena Biagi, Simon J. Puglisi, and Jaakko Vuohtoniemi.  Subset wavelet trees.  In Proc. 21st SEA, pages 4:1–4:14, 2023.  doi:10.4230/LIPIcs.SEA.2023.4.
  * [3] Jarno N. Alanko, Simon J. Puglisi, and Jaakko Vuohtoniemi.  Small searchable _$\kappa$_ -spectra via subset rank queries on the spectral burrows-wheeler transform.  In Proc. ACDA, 2023, pages 225–236, 2023.  doi:10.1137/1.9781611977714.20.
  * [4] Mai Alzamel, Lorraine A. K. Ayad, Giulia Bernardini, Roberto Grossi, Costas S. Iliopoulos, Nadia Pisanti, Solon P. Pissis, and Giovanna Rosone.  Comparing degenerate strings.  Fundam. Informaticae, 175(1-4):41–58, 2020.  doi:10.3233/FI-2020-1947.
  * [5] Jérémy Barbay, Francisco Claude, Travis Gagie, Gonzalo Navarro, and Yakov Nekrich.  Efficient fully-compressed sequence representations.  Algorithmica, 69(1):232–268, 2014.  doi:10.1007/S00453-012-9726-3.
  * [6] Jérémy Barbay, Meng He, J. Ian Munro, and Srinivasa Rao Satti.  Succinct indexes for strings, binary relations and multilabeled trees.  ACM Trans. Algorithms, 7(4):52:1–52:27, 2011.  doi:10.1145/2000807.2000820.
  * [7] Djamal Belazzougui, Patrick Hagge Cording, Simon J. Puglisi, and Yasuo Tabei.  Access, rank, and select in grammar-compressed strings.  In Proc. 23rd ESA, pages 142–154, 2015.  doi:10.1007/978-3-662-48350-3\\_13.
  * [8] Djamal Belazzougui and Gonzalo Navarro.  Optimal lower and upper bounds for representing sequences.  ACM Trans. Algorithms, 11(4):31:1–31:21, 2015.  doi:10.1145/2629339.
  * [9] David R. Clark and J. Ian Munro.  Efficient suffix trees on secondary storage (extended abstract).  In Proc. 7th SODA, pages 383–391, 1996.  URL: http://dl.acm.org/citation.cfm?id=313852.314087.
  * [10] Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen.  Covering problems for partial words and for indeterminate strings.  Theor. Comput. Sci., 698:25–39, 2017.  doi:10.1016/J.TCS.2017.05.026.
  * [11] Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, and Gonzalo Navarro.  Compressed representations of sequences and full-text indexes.  ACM Trans. Algorithms, 3(2):20, 2007.  doi:10.1145/1240233.1240243.
  * [12] Travis Gagie.  Rank and select operations on sequences.  In Encyclopedia of Algorithms, pages 1776–1780. 2016.  doi:10.1007/978-1-4939-2864-4\\_638.
  * [13] Simon Gog, Timo Beller, Alistair Moffat, and Matthias Petri.  From theory to practice: Plug and play with succinct data structures.  In Proc. 13th SEA, pages 326–337, 2014.
  * [14] Alexander Golynski, J. Ian Munro, and S. Srinivasa Rao.  Rank/select operations on large alphabets: a tool for text indexing.  In Proc. 15th SODA, pages 368–373, 2006.  URL: http://dl.acm.org/citation.cfm?id=1109557.1109599.
  * [15] Alexander Golynski, Alessio Orlandi, Rajeev Raman, and S. Srinivasa Rao.  Optimal indexes for sparse bit vectors.  Algorithmica, 69(4):906–924, 2014.  doi:10.1007/S00453-013-9767-2.
  * [16] Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter.  High-order entropy-compressed text indexes.  In Proc. 14th SODA, pages 841–850, 2003.
  * [17] Roberto Grossi, Rajeev Raman, Srinivasa Rao Satti, and Rossano Venturini.  Dynamic compressed strings with random access.  In Proc. 40th ICALP, pages 504–515, 2013.  doi:10.1007/978-3-642-39206-1\\_43.
  * [18] Meng He and J. Ian Munro.  Succinct representations of dynamic strings.  In Proc. 17th SPIRE, pages 334–346, 2010.  doi:10.1007/978-3-642-16321-0\\_35.
  * [19] Costas S. Iliopoulos, Laurent Mouchard, and Mohammad Sohel Rahman.  A new approach to pattern matching in degenerate DNA/RNA sequences and distributed pattern matching.  Math. Comput. Sci., 1(4):557–569, 2008.  doi:10.1007/S11786-007-0029-Z.
  * [20] Guy Jacobson.  Space-efficient static trees and graphs.  In Proc. FOCS, pages 549–554, 1989.  doi:10.1109/SFCS.1989.63533.
  * [21] Ian B Jeffery, Anubhav Das, Eileen O’Herlihy, Simone Coughlan, Katryna Cisek, Michael Moore, Fintan Bradley, Tom Carty, Meenakshi Pradhan, Chinmay Dwibedi, et al.  Differences in fecal microbiomes and metabolomes of people with vs without irritable bowel syndrome and bile acid malabsorption.  Gastroenterology, 158(4):1016–1028, 2020.
  * [22] Danyang Ma, Simon J Puglisi, Rajeev Raman, and Bella Zhukova.  On elias-fano for rank queries in fm-indexes.  In Proc. DCC, 2021, pages 223–232, 2021.
  * [23] Veli Mäkinen and Gonzalo Navarro.  Rank and select revisited and extended.  Theor. Comput. Sci., 387(3):332–347, 2007.  doi:10.1016/J.TCS.2007.07.013.
  * [24] Gonzalo Navarro and Yakov Nekrich.  Optimal dynamic sequence representations.  SIAM J. Comput., 43(5):1781–1806, 2014.  doi:10.1137/130908245.
  * [25] Gonzalo Navarro and Kunihiko Sadakane.  Fully functional static and dynamic succinct trees.  ACM Trans. Algorithms, 10(3):16:1–16:39, 2014.  doi:10.1145/2601073.
  * [26] Daisuke Okanohara and Kunihiko Sadakane.  Practical Entropy-Compressed Rank/Select Dictionary.  In Proc. 9th ALENEX, 2007.  doi:10.1137/1.9781611972870.6.
  * [27] Alberto Ordóñez Pereira, Gonzalo Navarro, and Nieves R. Brisaboa.  Grammar compressed sequences with rank/select support.  J. Discrete Algorithms, 43:54–71, 2017.  doi:10.1016/J.JDA.2016.10.001.
  * [28] Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti.  Succinct indexable dictionaries with applications to encoding _k_ -ary trees, prefix sums and multisets.  ACM Trans. Algorithms, 3(4):43, 2007.  doi:10.1145/1290672.1290680.

##  Appendix A Additional Data

|  $k$-mer Queries | Subset Rank Queries
---|---|---
| E. Coli | Metagenome | E. Coli | Metagenome
Data structure | Query | Space | Query | Space | Query | Space | Query | Space
| ($\mu$s) | (bpk) | ($\mu$s) | (bpk) | (ns) | (bps) | (ns) | (bps)
Matrix | 0.63 | 4.29 | 0.77 | 4.62 | 38.75 | 4.26 | 56.98 | 4.25
DSD (scan) | 3.00 | 2.61 | 3.75 | 2.70 | 210.23 | 2.57 | 311.33 | 2.48
Thm1(iii) | 3.87 | 3.68 | 4.95 | 3.91 | 435.28 | 3.64 | 546.89 | 3.60
DSD (rrr) | 13.21 | 2.38 | 15.17 | 2.46 | 850.99 | 2.34 | 1086.11 | 2.26
SIMD | 3.31 | 2.42 | 4.16 | 2.50 | 320.53 | 2.37 | 444.94 | 2.28
SWT (scan) | 1.63 | 4.53 | 1.96 | 4.87 | 129.44 | 4.49 | 170.44 | 4.49
SWT (split) | 4.93 | 3.17 | 6.06 | 3.21 | 436.69 | 3.13 | 620.47 | 2.96
SWT (rrr gen.) | 18.97 | 2.84 | 19.79 | 3.04 | 789.12 | 2.81 | 860.4 | 2.80
SWT (rrr) | 25.33 | 2.48 | 27.55 | 2.62 | 1384.0 | 2.45 | 1610.73 | 2.41
Split (plain) | 2.28 | 3.30 | 2.84 | 3.52 | 235.22 | 3.27 | 298.87 | 3.24
Split (ef) | 2.71 | 2.69 | 3.30 | 2.78 | 317.71 | 2.65 | 390.65 | 2.56
Split (rrr) | 4.70 | 2.54 | 5.54 | 2.65 | 393.14 | 2.51 | 471.30 | 2.44
Concat(ef) | 26.25 | 2.38 | 30.53 | 2.48 | 1372.2 | 2.35 | 1786.65 | 2.28
Table 1: The left half of the table shows the result for the $k$-mer query
test. The times are listed in microseconds per query, and space in the number
of bits per represented $k$-mer. The right half shows the result of the
subset-rank query test. Times are listed in nanoseconds per query, and space
in bits per symbol (i.e., the number of bits divided by $N$). There are five
groups of data structures, separated by horizontal lines; the benchmark
structure, our reductions, our structure using SIMD, the Subset Wavelet Trees
from [2], and the reductions from [3]. Each group is ordered from fastest to
slowest and largest to smallest, except for Thm1(iii) which breaks space
order. Each value in the table is the average of five measurements.

##  Appendix B Results for all Data Structures

This section elaborates on the data structures that were omitted from Sections
5.2 and 6. From [3], we omitted the structure Concat (plain), which is the
structure Concat (ef) explained in Section 5.2 parameterized with standard
SDSL bitvcectors instead. We also omitted Matrix (ef) and Matrix (rrr), which
is the benchmark solution parameterized with different types of bitvectors.

Furthermore, this section includes more parameterizations of our SIMD enhnaced
data structure. We elaborate on the SIMD structure from Section 5.2. DSD (SIMD
(i)) (which we refer to as SIMD (i) for simplicity) is the DSD parameterized
with the SIMD (i) structure, which supports rank queries on strings over the
alphabet $\\{0,1,2,3\\}$. As described in Section 5.2, the main idea is to
divide the string into blocks, precompute the answer to rank queries up to the
start of each block, and compute partial rank queries internally in blocks as
needed using SIMD. The width of the block is determined by the parameter $i$;
there are $512i$ characters stored per block (recall that the width of the
SIMD registers we used was $512$ bits). The blocks are stored as follows. Each
character in $\\{0,1,2,3\\}$ consists of two bits. We separate the string
represented by the block into two bitstrings; one consisting of the low bits,
and one of the high bits. To compute partial rank queries, we use the
operation vpternlogq, which given three vectors and an $8$-bit integer value
evaluates _any_ three-variable boolean function bit-wise for the three vectors
(the $8$-bit integer describes the result column of the three-variable truth
table, which has eight rows). The operation also accepts an additional
integer, used to mask out results if they are not needed for the computation.
To answer rank queries, we traverse the low and high bitstrings, using
vpternlogq to find occurrences of the queried character and the mask to filter
out results occurring after the queried index. The version of the SIMD data
structure in Sections 5.2 and 6 is SIMD (8).

The results for all the structures on the metagenome data set can be seen in
Figure 3 ($k$-mer search test) and Figure 4 (rank query benchmark). All the
data, for all structures, both data sets, and both tests, can be seen in Table
2.

Figure 3: Note that the $x$-axis is truncated. Shows the performance of all data structures for the $k$-mer search test on the metagenome data set. The two gray lines represent the performance of the benchmark solution “Matrix”. The crosses indicate our data structures and the circles indicate the data structures from [2, 3]. Figure 4: Note that the $x$-axis is truncated. Shows the performance of all data structures for the rank query benchmark. The space is in number of bits per symbol, i.e., $\text{bits}/N$. The two gray lines represent the performance of the benchmark solution “Matrix”. The crosses indicate our data structures and the circles indicate the data structures from [2, 3]. |  $k$-mer Queries | Subset Rank Queries
---|---|---
| E. Coli | Metagenome | E. Coli | Metagenome
Data structure | Query | Space | Query | Space | Query | Space | Query | Space
| ($\mu$s) | (bpk) | ($\mu$s) | (bpk) | (ns) | (bps) | (ns) | (bps)
Matrix | 0.63 | 4.29 | 0.77 | 4.62 | 38.75 | 4.26 | 56.98 | 4.25
Matrix (ef) | 0.92 | 4.07 | 1.24 | 4.61 | 73.9 | 4.04 | 94.4 | 4.25
Matrix (rrr) | 5.28 | 3.38 | 5.96 | 3.66 | 301.7 | 3.34 | 367.45 | 3.37
DSD (scan) | 3.0 | 2.61 | 3.75 | 2.7 | 210.23 | 2.57 | 311.33 | 2.48
Thm1(iii) | 3.87 | 3.68 | 4.95 | 3.91 | 435.28 | 3.64 | 546.89 | 3.6
DSD (rrr) | 13.21 | 2.38 | 15.17 | 2.46 | 850.99 | 2.34 | 1086.11 | 2.26
SIMD (4) | 2.98 | 2.49 | 3.79 | 2.58 | 289.54 | 2.42 | 405.88 | 2.33
SIMD (8) | 3.31 | 2.42 | 4.16 | 2.5 | 320.53 | 2.37 | 444.94 | 2.28
SIMD (16) | 3.67 | 2.39 | 4.58 | 2.47 | 371.87 | 2.35 | 500.97 | 2.26
SIMD (32) | 5.35 | 2.37 | 6.34 | 2.45 | 447.28 | 2.34 | 585.65 | 2.25
SWT (scan) | 1.63 | 4.53 | 1.96 | 4.87 | 129.44 | 4.49 | 170.44 | 4.49
SWT (split) | 4.93 | 3.17 | 6.06 | 3.21 | 436.69 | 3.13 | 620.47 | 2.96
SWT (rrr gen.) | 18.97 | 2.84 | 19.79 | 3.04 | 789.12 | 2.81 | 860.4 | 2.8
SWT (rrr) | 25.33 | 2.48 | 27.55 | 2.62 | 1384.0 | 2.45 | 1610.73 | 2.41
Concat(plain) | 2.53 | 3.74 | 3.51 | 4.02 | 375.44 | 3.71 | 491.55 | 3.7
Concat(ef) | 26.25 | 2.38 | 30.53 | 2.48 | 1372.2 | 2.35 | 1786.65 | 2.28
Split (plain) | 2.28 | 3.3 | 2.84 | 3.52 | 235.22 | 3.27 | 298.87 | 3.24
Split (ef) | 2.71 | 2.69 | 3.3 | 2.78 | 317.71 | 2.65 | 390.65 | 2.56
Split (rrr) | 4.7 | 2.54 | 5.54 | 2.65 | 393.14 | 2.51 | 471.3 | 2.44
Table 2: The left half of the table shows the result for the $k$-mer query
test. The times are listed in microseconds per query, and space in the number
of bits per represented $k$-mer. The right half shows the result of the
subset-rank query test. Times are listed in nanoseconds per query, and space
in bits per symbol (i.e., the number of bits divided by $N$). There are six
groups of data structures, separated by horizontal lines; the variants of the
benchmark structure, our reductions, our structure using SIMD, the Subset
Wavelet Trees from [2], the “Concat” reduction from [3], and the “Split”
reduction from [3]. Each group is ordered from fastest to slowest and largest
to smallest, except for Thm1(iii) which breaks space order. Each value in the
table is the average of five measurements.


11institutetext: Ontario Tech University, Oshawa ON L1L 1C1, Canada
11email<EMAIL_ADDRESS>
# Targeted Honeyword Generation with Language Models

Fangyi Yu 11 0000-0002-6461-5720 Miguel Vargas Martin 11 0000-0001-8169-6836

###### Abstract

Honeywords are fictitious passwords inserted into databases in order to
identify password breaches. The major difficulty is how to produce honeywords
that are difficult to distinguish from real passwords. Although the generation
of honeywords has been widely investigated in the past, the majority of
existing research assumes attackers have no knowledge of the users. These
honeyword generating techniques (HGTs) may utterly fail if attackers exploit
users’ personally identifiable information (PII) and the real passwords
include users’ PII. In this paper, we propose to build a more secure and
trustworthy authentication system that employs off-the-shelf pre-trained
language models which require no further training on real passwords to produce
honeywords while retaining the PII of the associated real password, therefore
significantly raising the bar for attackers.

We conducted a pilot experiment in which individuals are asked to distinguish
between authentic passwords and honeywords when the username is provided for
GPT-3 and a tweaking technique. Results show that it is extremely difficult to
distinguish the real passwords from the artifical ones for both techniques. We
speculate that a larger sample size could reveal a significant difference
between the two HGT techniques, favouring our proposed approach.

###### Keywords:

honeyword natural language processing language models.

##  1 Introduction

Passwords have dominated the authentication system for decades, despite their
security flaws compared to competing techniques such as cognitive
authentication [15], biometrics [23] and tokens [25]. The irreplaceable is
primarily due to its incomparable deployability and usability [6]. However,
current password-based authentication systems store sensitive password files
that make them ideal targets for attackers because if successfully obtained
and cracked (recovering the hashed passwords’ plain-text representations), an
adversary may impersonate registered users in an undetectable fashion [28].
Numerous prestigious online services have been infiltrated, for example,
Yahoo!, RockYou, Zynga, resulting in the exposure of millions of credentials.
Unfortunately, there is often a large delay between a credential database’s
breach and its detection; estimates place the average latency at 287 days [1].
The resulting window of vulnerability enables attackers to crack passwords
offline (if the stolen credential database contains encrypted passwords rather
than plain-text passwords); determine the value of these passwords by probing
their associated accounts, and then use them directly to extract value or sell
them via illicit forums profiting with stolen credentials [27]. Normally, the
longer it takes to detect and remediate a data breach, the more expensive it
is. More precisely, data breaches that take more than 200 days to identify and
contain cost an average of 4.87 million, compared to 3.61 million for breaches
that take fewer than 200 days to identify and manage [1]. As a result, it is
vital to have active, timely password-breach detection systems in place to
allow immediate counter-actions.

One way to reduce the cost of password breaches is to make offline guessing
harder. A variety of ways have been proposed in the literature, including
machine-dependent functions [4], external password-hardening services [19],
and distributed cryptography [9]. All of these approaches, however, have major
disadvantages, such as low scalability or a need for large modifications to
the server-side and client-side authentication systems, which prevent the
community from implementing them.

Another promising approach is to shorten the latency between password breaches
and detection. Juels and Rivest suggest the use of honeywords as a potential
method for efficiently detecting password leaks [17]. According to their
proposal, a website could store decoy passwords, called honeywords, alongside
real passwords in its credential database, so that even if an attacker steals
and reverts the password file containing the users’ hashed passwords, they
must still choose a real password from a set of $k$ distinct sweetwords, where
a real password and its associated honeywords are referred to as sweetwords.
The attacker’s use of a honeyword could cause the website to become aware of
the breach. Notably, honeywords are only beneficial if they are difficult to
distinguish from real-world passwords; otherwise, a knowledgeable attacker may
be able to recognize them and compromise their security. Thus, when
implementing this security feature into current authentication systems, the
honeyword generating process is critical.

Table 1: Data breaches containing PII and passwords in the past five years

Dataset | Number of Items | Year | Type of PII breached
---|---|---|---
Neiman Marcus | 4,800,000 | 2021 | Name, Encrypted Password, Security questions, Financial information
CAM4 | 10,880,000,000 | 2020 | Name, Email, Encrypted Password, Chat transcripts, IP, Payment logs
Canva | 137,000,000 | 2019 | Name, Email, Encrypted Password
Quora | 100,000,000 | 2018 | Name, Email, Encrypted Password, Questions and answers posted
Yahoo | 3,000,000,000 | 2017 | Name, Email, Encrypted Password, DoB, Security question and answer

###  1.1 Honeywords for Targeted Attacks

The biggest challenge of designing a honeyword generation technique is to
generate honeywords that are resistant to targeted attacks. For targeted
attacks, attackers exploit users’ PII to guess passwords, which increases the
likelihood of users’ accounts being compromised. This is a critical problem
for two reasons. First, numerous PII and passwords become widely accessible as
a result of ongoing data breaches [2, 1]. Second, people are used to create
easy-to-remember passwords using their names, birthdays, and their variants
[29]. Once an attacker obtains users’ PII, and if only one sweetword in a
user’s sweetword list contains the user’s PII, it is highly likely that this
sweetword is the real password and others are fake. For example, for a
sweetword list “liyaodong007, gaby1124, abg71993, australiaisno#1,
soloelbambino, k646321102, noviembre9101, blueluna17, usa0858199600,
kirsten03” which are generated using the real password “liyaodong007” in the
linkedin dataset and the HGT proposed in [12]. In a nutshell, this HGT is
first trained on a real password dataset, and it converts all real passwords
in the dataset into vectors using a word embedding technique called fasttext.
For each user, the HGT assigns $k-1$ honeywords to the $k-1$ real passwords
that have the closest distance to this user’s actual password based on cosine
similarity. In this case, if the attacker has no information about the user,
it will be difficult to determine which of the ten sweetwords is the real
password, since all of honeywords are from data breaches and are legitimate
passwords belonging to other users. However, if the attacker knows the user’s
email address is<EMAIL_ADDRESS>it is quite straightforward to deduce
that “liyaodong007” is this user’s real password and the others are all fake.

Following the introduction of the honeywords security mechanism by Juels and
Rivest [17], the academic community has been actively exploring the technique.
However, to our knowledge, only one paper [30] concentrated on the production
of honeywords in a targeted manner. All other papers make the invalid
assumption that attackers have no knowledge about the users. Each year, as
demonstrated in Table 1, billions of password datasets including PII are
leaked. Attackers might use the PII to determine which sweetword is the real
password. If all the sweetwords do not include any PII existing in the
password breach, the attackers may still create a knowledge map for each user
by searching their information purposefully through social media and search
engines using the known PII exposed in data breaches. This is especially a
concern if the user is a celebrity or a politician. Compromised accounts may
have substantial financial, political, and societal consequences.

Figure 1: Password (PW) authentication with honeywords.

###  1.2 Related Work

Numerous studies have been conducted on the non-targeted honeyword generation
method. The majority of these HGTs fall into two categories: chaffing-by-
tweaking and chaffing-with-a-password-model. Chaffing-by-tweaking is mostly
based on the substitution of random letters, digits, and symbols. For
instance, given the real password “$deshaun96$”, we could get honeywords
“$deshaun87$, $deshAUn66$, $DesHaun56$” via tweaking. However, as Wang et al.
[28] demonstrate, this strategy is indeed vulnerable. While honeywords
generated using the chaffing-with-a-password-model approach are more resistant
to attacks, they do have certain drawbacks. Bojinov et al. [5] proposed
Kamouflage, that first tokenize the user’s real passwords into a collection of
tokens, and then substitutes each token with a random one that matches the
token’s type. For instance, “$jones34monkey$” is tokenized as
“$l_{5}d_{2}l_{6}$” (a five-letter word followed by two digits and a six-
letter word), indicating that some possible honeywords are “$apple10laptop$,
$tired93braces$, $hills28highly$”. This technique, as outlined in [12],
demands considerable modifications on the client-side authentication system,
which has a significant impact on usability. Additionally, it is incapable of
generating honeywords of varying length or structure, thus limiting the
spectrum of possible honeywords.

Erguler [14] proposed a different technique in which honeywords are derived
from the system’s current user passwords. In this case, all honeywords are
realistic and adhere to the operator’s password creating policy. However,
their HGT is restricted by the limited number of viable honeywords created by
selecting genuine passwords from the website’s password corpus, which is
particularly the case if the website has a small user database.

To the best of our knowledge, there is only one publication that discusses how
to generate honeywords that are resistant to targeted attacks, which was
published in IEEE S&P’22 by Wang et al [30]. They first proposed four attack
models each representing a potential attacker $A$’s strategy, with each model
based on different information available to $A$ (e.g., public datasets, the
victim’s personal information and registration order). They further develop
four HGTs for each attack strategy, by using various representative
probabilistic password guessing models proposed in their previous paper [29].
These assumptions about attackers are flawed since we should anticipate the
attackers would utilize whatever information they can get to attack users’
accounts, particularly if the user is a person of interest. What we are
proposing is a much simpler and generalized approach. Rather than assuming
$A$’s attack strategy and creating HGTs accordingly, we construct honeywords
based on the information contained in the real password. The challenge is to
partition the real password into tokens while retaining tokens that correspond
to PII and replacing tokens that do not correspond to PII with random ones.
Consider the real password “liyaodong007”, the challenge is to produce
honeywords containing the token“liyaodong”, which is the user’s full name as
indicated by his/her email address. To do this, we propose to employ language
models, which are extensively used in the area of natural language processing
(NLP), to overcome this obstacle.

###  1.3 Our contribution

  * •

We are among the first to propose HGTs that are resistant to targeted attacks
in which attackers have access to users’ PII. In comparison to [30], our
solution is much simpler and can be adapted to defend against any form of
attack.

  * •

We are the first to use language models to create honeywords. We suggest
building honeywords using GPT-3, which has an easy operator implementation.
The off-the-shelf GPT-3 model can create high-quality honeywords that are
resistant to targeted attacks without being trained on real passwords. We
would like to draw the attention of researchers to use language models to
create honeywords that are resistant to targeted attacks, and thus build a
more trustworthy authentication system.

  * •

We conducted a pilot study to establish our method’s validity.

The remainder of the paper is structured as follows: Section 2 provides the
preliminaries for understanding our work. Section 3 introduces our approach to
generate honeywords in a targeted manner. Section 4 is the human study design
and evaluation. Section 5 discusses the limitations of our work and future
directions. Section 6 concludes our work.

##  2 Preliminaries

###  2.1 The Honeyword Mechanism

According to Juels and Rivest [17], the honeyword system is comprised of four
entities, as shown in Figure 1: a user $U_{i}$, an authentication server $S$,
a $honeychecker$, and the attacker $A$. User $U_{i}$ initially registers an
account($ID_{i}$, $PW_{i}$) on the server $S$. Apart from the standard user
registration processes, $S$ runs a command $GEN(k,PW_{i})$ to produce a list
of $k-1$ unique fake passwords (called honeywords) to be stored alongside
$U_{i}$’s true password $PW_{i}$, where $k=20$ as recommended in [17].
$PW_{i}$ and its $k-1$ honeywords are referred to as $k$ sweetwords.

###  2.2 Threat Model

Honeyword-enabled systems could reliably identify a password file leak by
pairing each user’s account with $k-1$ honeywords. The reason for this is that
even if attackers obtain a copy of the password file along with its hashing
parameters and salts, and successfully recover all the passwords via brute-
force or other password guessing techniques [13, 31, 20, 21] (be aware that at
this stage they know which $k$ sweetwords are associated with each user), they
must first distinguish each user’s true password from these $k$ sweetwords.
The system features honeychecker to aid in the usage of honeywords, and the
computer system could interact with the honeychecker whenever a login attempt
is made or users change their passwords. Additionally, the honeychecker is
capable of triggering an alert if an anomaly is discovered. The warning signal
may be sent to an administrator or to a third party other than the computer
system itself [17]. This approach is compatible with existing authentication
systems since it needs little adjustments to the server-side systems and no
alterations to the client-side systems; nevertheless, it is very reliable due
to the high probability of capturing adversaries. For instance, if the
likelihood of an attacker selecting each sweetword is uniform, the probability
of capturing an attacker is $3/4=75\%$ for $k=4$, and thus the probability
grows as $k$ increases.

Even though most passwords breached are encrypted, with the evolution of high-
performance computing equipment such as GPUs and large-scale distributed
clusters, attackers could eventually reverse the majority of password hashes
stored in password file [26]. As a result, once an attacker obtains any
password files, it is reasonable to assume that the overwhelming majority of
passwords can be brute-force cracked offline, and converted to their plain-
text version.

Table 2: Honeywords generated by GPT-3 when using different prompts. A more
specific prompt can produce higher-quality honeywords.

Prompt1 | Suggest three passwords that are similar to ”toby2009bjs”.
---|---
Honeywords | toby2009bjd, toby2009bjx, toby2009bjz
Prompt2 | Suggest three words that look like ”toby2009bjs”.
Honeywords | toy2009bjs, tab2009bjs, boy2009bjs

Table 3: Honeywords generated by GPT-3 when using different temperatures and
given the prompt ”Suggest five words that are similar to ”toby2009bjs””. A
higher temperature will result in more diverse honeywords.

Temperature | Honeywords
---|---
0 | toby2009bjd, toby2009bjx, toby2009bjz, toby2009bjf, toby2009bjh
1 | Toby2009BJS, toby2009bjs1, tobybjs2009, Bjs2009toby, bjs2009toby1

###  2.3 Language Model

Language models can learn the probabilities of occurrences of a series of
words in a regularly spoken language (for example, English) and predict the
next potential word in that sequence. Generative Pre-trained Transformer 3
(GPT-3) is an autoregressive language model that uses deep learning to
generate text that appears to be written by a person. It was introduced in
2020 by Elon Musk et al.’s AI research lab, OpenAI, and excels at a variety of
NLP tasks, including translation, question-answering, and cloze [8]. The model
was trained on trillions of words in text documents. It turns the words into
vectors, or mathematical representations, and then decode the encoded text
into human-readable phrases. It comprehends and processes text by breaking it
into tokens. Tokens may be single words or groups of characters. For instance,
the word “beautiful” could be split into the tokens “beau”, “ti” and “ful”,
but a short and common word such as “big” is a single token. The model can be
utilized to execute NLP tasks without requiring fine-tuning on particular
downstream task datasets. It is capable of producing texts that are difficult
for humans to differentiate from human-written articles.

Since the introduction of Generative Pre-trained Transformers, they have been
extensively investigated in a variety of domains, including creating summaries
of media dialogues [11], generating code from natural-language instructions
[10], generating passphrases [16], and generating graphics from text
descriptions [22]. To the best of our knowledge, we are the first to employ
GPT-3 in the sphere of computer security, to generate honeywords that are
resistant to targeted attacks.

##  3 Approach

###  3.1 Use GPT-3 for targeted honeyword generation

We propose to use GPT-3 to generate honeywords that are robust to targeted
attacks. When generating honeywords, GPT-3 first splits its input, the real
password, into tokens. For example, depending on the $temperature$,
“$toby2009bjs$” may be tokenized to “$toby$”, “$2009$” and “$b$”, “$j$”,
“$s$”. When given a $prompt$, GPT-3 generates a text $completion$ that tries
to match the context or pattern specified. Since honeyword is a new term
specified in the computer security domain and does not exist in the GPT-3’s
training data, we need to specify what the model should do by giving it a
prompt, for example, “Suggest five passwords that are similar to
“$toby2009bjs$” .” It will then produce outputs “toby2009bjd, toby2009bjf,
toby2009bjg, toby2009bjh, toby2009bjk.” The quality and the diversity of the
output depends on three attributes: prompt, temperature and examples given to
the model.

The prompt. The prompt is the instruction GPT-3 received. The quality of the
prompt can determine the quality of the generated honeywords. By experiments,
we found that the more concise, specific the prompt is, the higher the quality
of the honeywords, as shown in Table 2.

(a) Give GPT-3 no examples when generating honeywords. The honeywords simply
adds on the last digit.

(b) Give GPT-3 two examples for generating better honeywords. Through
examples, the model can learn the expected pattern of honeywords and create
honeywords with the same pattern as the real password.

Figure 2: The comparison of honeywords generated by GPT-3 in two conditions:
given no examples and given two examples. The model is able to generate
honeywords that conform to the operators’ expectations by given
demonstrations.

The temperature. The temperature is a numeric variable between 0 and 1 that
effectively regulates the model’s degree of confidence when generating
predictions. A lower temperature implies that the model will take fewer risks,
and the honeywords created will be more precise and predictable. While
increasing the temperature results in more diversified honeywords, a drawback
is it may also cause the PII in genuine passwords to be replaced with other
words. Table 3 contains examples of honeywords formed at temperatures 0 and 1.

Zero-shot learning and Few-shot learning. Zero-shot learning refers to a
situation in which no demonstrations are permitted and the model is given
simply a plain language description of the task. In comparison, few-shot
learning refers to a situation in which the model is given a few
demonstrations of the task during inference time, but the model is not re-
trained on the demonstrations. This is particularly advantageous since many
websites have varying policies regarding password creation, such as begining
with letters and requiring uppercase, lowercase, symbols, and numbers. When
the operators demonstrate how they want the honeywords to appear, GPT-3 will
generate honeywords that match the examples. An image illustration is in
Figure 2.

###  3.2 How Operators can use GPT-3 for targeted honeyword generation

Integration of GPT-3 into the operator’s system for honeyword production is
relatively simple. Unlike other HGTs that require to be trained on a leaked
password dataset [12], our HGT only requires the operator to simply
incorporate the OpenAI API [3], and give a specific prompt and temperature in
the $GEN(k,PW_{i}$) command and no training on leaked password is required.

##  4 Evaluation

We evaluated our HGT by conducting human studies and wanted to validate our
hypothesis: When a victim’s username is provided, attackers need more attempts
to correctly find the victim’s real password when honeywords are generated by
GPT-3 than the control condition.

For the HGT in the control condition, we use the chaffing-by-tweaking HGT
which was initially presented in [17] and mainly relies on random letter,
digit, and symbol substitution. We choose to use chaffing-by-tweaking instead
of other recently proposed methods in the literature because other methods are
more vulnerable to targeted attacks, with a typical example mentioned in
Section 1.1, and some more examples shown in Table 4. Dionysiou et al. [12]
highlight the intricacy of developing tweaking rules in such a way that it
could be difficult for an attacker to distinguish the password from its
changed versions. For example, if a chaffing-by-tweaking strategy randomly
perturbs the last three characters of a password, the adversary may easily
conclude that the authentic password is the first one in the instances
“18!morning”, “18!morniey”, and “18!gorndge”. Thus, they replace all
occurrences of a particular symbol in a given password with a randomly chosen
alternate symbol, lower-case each letter in a password with probability
$p=0.3$, upper-case each letter in a password with probability $f=0.03$, and
replace each digit occurrence with probability $q=0.05$. [12] contains the
pseudocode and rationale for the assignment of $p,q$, and $f$. A few examples
of honeywords developed by tweaking are included in Table 5. Table 6 shows
some honeyword samples generated by GPT-3 for comparison.

Table 4: Honeyword samples generated by fasttext. The word embedding machine learning model fasttext has been trained on a subset of the rockyou dataset. Generated honeywords usually do not contain any current-user-specific PII. Passwords | deshaun96 | dafnny_24 | toby2009bjs
---|---|---|---
Honeywords by fasttext | foodlion21 | snuffy22 | yaiy236
cutechica1 | octavia3 | cooneoos3a
felli1330 | Bushido07 | kmt3299
boedha21 | Dampire2 | broloond
Table 5: Honeyword samples generated by tweaking. Passwords | deshaun96 | dafnny_24 | toby2009bjs
---|---|---|---
Chaffed Honeywords | DeShauN37 | dafnny=96 | toBy2009Bjs
deshaun87 | dafNnY$<$44 | tOby2010bjS
deshAUn66 | dAfnny+47 | tobY1009bjs
DesHaun56 | Dafnny75 | TOby3509bJs
Table 6: Honeyword samples generated by GPT-3. The model does not need to be fine-tuned on any dataset, giving it a proper prompt and temperature is enough to generate high-quality honeywords. The real passwords are from the rockyou dataset. The honeywords generated are in line with people’s password creation behavior: making minor variations on existing passwords while keeping the tokens with semantic meaning intact. Passwords | deshaun96 | dafnny_24 | toby2009bjs
---|---|---|---
Honeywords by GPT-3 | deshaun97 | dafnny_25 | toby2009bjd
deshaun98 | dafnny_28 | toby2009bjx
deshaun02 | dafnny_29 | toby2009bjz
deshaun07 | dafnny_23 | toby2009bjh

###  4.1 Experiment Design

We conducted a pilot study and asked two of the researchers involved in this
work to answer a survey containing questions for both HGTs. Our study did not
require research ethics approval since it only involved authors of this
research work and it was non-intrusive with no potential risks identified. In
our experiment, we have one independent variable: the type of HGT; two
conditions: GPT-3 and tweaking; and one dependent variable: the number of
attempts required to find the real password.

Participants were required to answer 12 rank-order questions, which match 6
sets of honeyword samples produced from each of the two HGTs. Each question
has 19 honeywords and 1 real password belonging to different users. The order
of the 20 sweetwords were randomized. The participants were asked to sort the
20 sweetwords in each question according to their level of confidence that the
sweetword is a real password, and the user’s username is provided. At the end
of the survey, we asked participants how hard the task is, and there are five
choices ranging from “not hard at all” to “extremely hard”, as shown in
Appendix LABEL:sentimental.

Dataset. We generated honeywords based on real passwords from a leaked
compilation of various password breaches over time. The dataset was first
discovered by 4iQ in the Dark Web1111.4 Billion Clear Text Credentials
Discovered in a Single Database: https://medium.com/4iqdelvedeep/1-4-billion-
clear-text-credentials-discovered-in-a-single-database-3131d0a1ae14. The
dataset consists of 1.4 billion email-password pairs, with 1.1 billion unique
emails and 463 million unique passwords. Duplicate email-password pairs were
removed by an unknown curator. The listed leaks are from websites such as
Canva, Chegg, Dropbox, LinkedIn, Yahoo!, Poshmark, etc. We intentionally chose
the email-password pairs where the password includes information from the
email as our real password candidates. In the real world scenario, the
password may not contain information in the email address, but it may contain
other PII, and we assume that the attacker could have access to these PII. Due
to the constraint of the data we have, we only use email address as the PII in
the experiments. To alleviate participants’ cognitive burden, we extract the
part before the symbol “@” as each user’s username and provide the username
instead of email address to participants.

To mitigate the negative impacts of learning effects and fatigue caused by the
within-group experiment, we employed the Balanced Latin Square Design [7], in
which each HGT appears the same amount of times as the first and second. Table
7 illustrates the sequence in which each HGT appears in the survey’s 12
questions.

Table 7: The order of each HGT appearing in the 12 survey questions. GPT-3 | Tweaking
---|---
Tweaking | GPT-3
GPT-3 | Tweaking
Tweaking | GPT-3
GPT-3 | Tweaking
Tweaking | GPT-3

As discussed in Section 3.1, the prompt, temperature and given examples can
affect the quality of GPT-3 generated honeywords. For the pilot experiment, we
choose to use a temperature of 0.65, and give the model instruction of
“Suggest 19 distinct passwords that are similar to REAL PASSWORD, and are
passwords that a LinkedIn user with username USERNAME would use.”

###  4.2 Results

Our analysis is based on the responses to our survey that each participant
provided. We want to determine if there is a significant difference in the
average number of attempts required for users to properly guess the real
password in the GPT-3 condition compared with the control condition.

We concatenated the responses for each HGT and got a dataset containing two
columns (the two HGTs), and 12 ($6\times 2$) rows, where each value represents
the attempts needed to find the real password in one of the questions in the
corresponding HGT. We analyzed the data using a paired-samples t-test to
examine if there are significant difference between attempts required to find
the real password for GPT-3 vs tweaking. As a result, due to the sample size
being too small, we did not find a significant difference between the attempts
required to find the real passwords in the two conditions when users’ username
is provided. We anticipate that if we used a large enough sample size, a
significant difference would be observed between the two conditions.
Nonetheless, both participants expressed that the task was extremely difficult
to complete, and they took an average of 17 minutes and 7 seconds to complete
all 12 questions. A sample question in the survey is provided in Appendix
LABEL:sample.

##  5 Discussion

We talk about the limitations of our study and future directions in this
section.

Quantitative Evaluation. Targeted online password attack is an underestimated
concern compared with trawling attacks [29]. We are the second to work on
targeted honeyword generation techniques, and the first to use language
models, notably GPT-3, to produce honeywords. We are highly confident about
the novelty and significance of our methodology. However, because there are
too few works being done in this field, we do not have proper benchmarks in
targeted attacks that can be used for our evaluation process. An attack model
is required to generate the commonly used metrics, namely the flatness and
success-number graphs [28], but there is no generalized attack model that can
be used for targeted purposes; the most popular Normalized Top-PW attack model
is for trawling attacks [32] in which the attackers are assumed to know
nothing about the victims. We recognize that our technique lacks quantitative
assessment, and we are developing quantitative analysis to demonstrate the
resilience of our HGT against targeted attacks. We also intend to draw the
community’s attention to targeted scenarios, since trawling situations have
been intensively studied, but targeted honeyword generation and attack models
are under-researched yet a pressing problem, as outlined in Section 1.1.

Qualitative Evaluation. The pilot study shows distinguishing between the real
password and honeywords is an extremly tough task, although there is not a
significant difference between the GPT-3 and tweaking HGTs since we conducted
experiments only with two participants. We plan to conduct a human study with
a larger sample size via crowd-sourcing platforms, and we speculate that a
larger sample size will result in a significant difference between the two
HGTs.

Irreversibility. The irreversibility of a HGT is critical. We need to make
sure that even when attackers know the prompt and the temperature we were
using for generating honeywords, they still cannot reproduce the honeywords we
generated. This is ensured by careful prompt-engineering [18, 24] and
temperature setting. We suggest to set temperature to 1 to get the most
randomness [8], and after experimenting with various prompts, we decided to
use the prompt ”Derive 19 words that are similar to $realpassword$, and
contain the word $PII$. The length of the words should be more than 10.” since
it generates the most diversified honeywords compared with other prompts we
experimented with, and the honeywords generated each time is different.

##  6 Conclusions

In this paper, we propose a novel HGT which utilizes GPT-3 to generate high-
quality honeywords that contain PII existing in users’ real passwords.
Honeywords generated by GPT-3 are robust to targeted attacks where attackers
get access to both breached password databases and users’ personal
identifiable information. Unlike other machine learning-based HGTs, GPT-3 can
be easily integrated into any current password-based authentication system
without any further training on real passwords. Additionally, we compared
GPT-3’s performance to a tweaking technique by conducting a human study with
two researchers. It is proved that to find the real password among all
sweetwords is an extremely difficult task and a larger sample size may be
required to show a significant difference between the two HGTs.

## Acknowledgement

The authors acknowledge the support of the Natural Sciences and Engineering
Research Council of Canada (NSERC), funding reference number RGPIN-2018-05919.

## References

  * [1] Ibm security: Cost of a data breach report 2021. https://www.ibm.com/security/data-breach (2021), [Online; accessed 01-Jan-2022]
  * [2] Have i been pwned. https://haveibeenpwned.com/ (2022), [Online; accessed 29-March-2022]
  * [3] Openai api. https://openai.com/api/ (2022), [Online; accessed 31-May-2022]
  * [4] Almeshekah, M.H., Gutierrez, C.N., Atallah, M.J., Spafford, E.H.: Ersatzpasswords: Ending password cracking and detecting password leakage. In: Proceedings of the 31st Annual Computer Security Applications Conference. pp. 311–320 (2015)
  * [5] Bojinov, H., Bursztein, E., Boyen, X., Boneh, D.: Kamouflage: Loss-resistant password management. In: European Symposium on Research in Computer Security. pp. 286–302. Springer (2010)
  * [6] Bonneau, J., Herley, C., Van Oorschot, P.C., Stajano, F.: The quest to replace passwords: A framework for comparative evaluation of web authentication schemes. In: 2012 IEEE Symposium on Security and Privacy. pp. 553–567. IEEE (2012)
  * [7] Bradley, J.V.: Complete counterbalancing of immediate sequential effects in a latin square design. Journal of the American Statistical Association 53(282), 525–528 (1958)
  * [8] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J.D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.: Language models are few-shot learners. Advances in neural information processing systems 33, 1877–1901 (2020)
  * [9] Camenisch, J., Lehmann, A., Neven, G.: Optimal distributed password verification. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. pp. 182–194 (2015)
  * [10] Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H.P.d.O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al.: Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374 (2021)
  * [11] Chintagunta, B., Katariya, N., Amatriain, X., Kannan, A.: Medically aware gpt-3 as a data generator for medical dialogue summarization. In: Machine Learning for Healthcare Conference. pp. 354–372. PMLR (2021)
  * [12] Dionysiou, A., Vassiliades, V., Athanasopoulos, E.: Honeygen: Generating honeywords using representation learning. In: Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security. pp. 265–279 (2021)
  * [13] Dürmuth, M., Angelstorf, F., Castelluccia, C., Perito, D., Chaabane, A.: Omen: Faster password guessing using an ordered markov enumerator. In: International Symposium on Engineering Secure Software and Systems. pp. 119–132. Springer (2015)
  * [14] Erguler, I.: Achieving flatness: Selecting the honeywords from existing user passwords. IEEE Transactions on Dependable and Secure Computing 13(2), 284–295 (2015)
  * [15] Hopper, N.J., Blum, M.: Secure human identification protocols. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 52–66. Springer (2001)
  * [16] Jagadeesh, N., Vargas Martin, M.: Alice in passphraseland: Assessing the memorability of familiar vocabularies for system-assigned passphrases (2021). https://doi.org/10.48550/ARXIV.2112.03359, https://arxiv.org/abs/2112.03359
  * [17] Juels, A., Rivest, R.L.: Honeywords: Making password-cracking detectable. In: Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security. pp. 145–160 (2013)
  * [18] Kojima, T., Gu, S.S., Reid, M., Matsuo, Y., Iwasawa, Y.: Large language models are zero-shot reasoners. arXiv preprint arXiv:2205.11916 (2022)
  * [19] Lai, R.W., Egger, C., Schröder, D., Chow, S.S.: Phoenix: Rebirth of a cryptographic password-hardening service. In: 26th USENIX Security Symposium (USENIX Security 17). pp. 899–916 (2017)
  * [20] Melicher, W., Ur, B., Segreti, S.M., Komanduri, S., Bauer, L., Christin, N., Cranor, L.F.: Fast, lean, and accurate: Modeling password guessability using neural networks. In: Proceedings of the 25th USENIX Conference on Security Symposium. pp. 175–191 (2016)
  * [21] Pasquini, D., Gangwal, A., Ateniese, G., Bernaschi, M., Conti, M.: Improving password guessing via representation learning. In: 2021 IEEE Symposium on Security and Privacy (S&P). pp. 1382–1399. IEEE (2021)
  * [22] Ramesh, A., Pavlov, M., Goh, G., Gray, S., Voss, C., Radford, A., Chen, M., Sutskever, I.: Zero-shot text-to-image generation. In: International Conference on Machine Learning. pp. 8821–8831. PMLR (2021)
  * [23] Ratha, N.K., Connell, J.H., Bolle, R.M.: Enhancing security and privacy in biometrics-based authentication systems. IBM systems Journal 40(3), 614–634 (2001)
  * [24] Reynolds, L., McDonell, K.: Prompt programming for large language models: Beyond the few-shot paradigm. In: Extended Abstracts of the 2021 CHI Conference on Human Factors in Computing Systems. pp. 1–7 (2021)
  * [25] Roche, T., Lomné, V., Mutschler, C., Imbert, L.: A side journey to titan. In: 30th USENIX Security Symposium (USENIX Security 21). pp. 231–248 (2021)
  * [26] Sprengers, M.: Gpu-based password cracking. On the Security of Password Hashing Schemes regarding Advances in Graphics Processing Units, Radboud University Nijmegen (2011)
  * [27] Thomas, K., Li, F., Zand, A., Barrett, J., Ranieri, J., Invernizzi, L., Markov, Y., Comanescu, O., Eranti, V., Moscicki, A., et al.: Data breaches, phishing, or malware? understanding the risks of stolen credentials. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. pp. 1421–1434 (2017)
  * [28] Wang, D., Cheng, H., Wang, P., Yan, J., Huang, X.: A security analysis of honeywords. In: Network and Distributed System Security (NDSS) Symposium 2018\. pp. 1–16 (10 2018). https://doi.org/10.14722/ndss.2018.12345
  * [29] Wang, D., Zhang, Z., Wang, P., Yan, J., Huang, X.: Targeted online password guessing: An underestimated threat. In: Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. pp. 1242–1254 (2016)
  * [30] Wang, D., Zou, Y., Dong, Q., Song, Y., Huang, X.: How to attack and generate honeywords. In: 2022 IEEE Symposium on Security and Privacy. pp. 489–506. IEEE (2022)
  * [31] Weir, M., Aggarwal, S., De Medeiros, B., Glodek, B.: Password cracking using probabilistic context-free grammars. In: 2009 30th IEEE Symposium on Security and Privacy. pp. 391–405. IEEE (2009)
  * [32] Yu, F., Martin, M.V.: Gnpassgan: Improved generative adversarial networks for trawling offline password guessing. In: 2022 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW). pp. 10–18 (2022)