$\textit{U}(\delta,\alpha)\allowbreak=\allowbreak\operatornamewithlimits{\displaystyle\mathbb{E}}_{\begin{subarray}{c}a\leftarrow\alpha\\\
\end{subarray}}\;\mathbb{V}\left[\pi,{{\osum_{d\leftarrow\delta}}}{C_{da}}\right].$
For each pure strategy profile $(d,a)$, the payoff of the game will be the
posterior Bayes vulnerability of the resulting channel $C_{da}$ (since, if we
are measuring the information leakage, the prior vulnerability is the same for
every channel once the prior is fixed).

In the $3$-bit password scenario, the attacker’s actions
$\mathcal{A}=\\{000,001,010,011,100,101,110,111\\}$ are all possible $3$-bit
low-inputs, and the defender’s $\mathcal{D}=\\{123,132,213,231,312,321\\}$ are
all possible versions of the password checker (each action represents the
order in which the $3$ bits are checked). Table 4 depicts the corresponding
payoffs of all $48$ possible resulting channels $C_{ad}$ with
$d\in\mathcal{D}$, $a\in\mathcal{A}$, when the prior is still
$\hat{\pi}=(0.0137,0.0548,0.2191,\allowbreak 0.4382,\allowbreak
0.0002,\allowbreak 0.0002,\allowbreak 0.0548,\allowbreak 0.2191)$. Note that
the attacker’s and defender’s actions substantially affect the effectiveness
of the attack: vulnerability ranges between 0.4934 and 0.9311 (and so
multiplicative leakage is in the range between an increase of $12\%$ and one
of $112\%$). Using techniques from Alvim et al. (2017), we can compute the
best (mixed) strategy for the defender in this game, which turns out to be

$\displaystyle\delta^{*}=(0.1667,0.1667,0.1667,0.1667,0.1667,0.1667).$

$\begin{array}[]{c|c||c|c|c|c|c|c|c|c|}\lx@intercol\hfil\hfil\lx@intercol&\lx@intercol\hfil\textbf{Attacker's
action $a$}\hfil\lx@intercol\\\
\cline{2-10}\cr&U(d,a)&000&001&010&011&100&101&110&111\\\
\cline{2-10}\cr\cline{2-10}\cr\hbox{\multirowsetup\rotatebox[origin={c}]{90.0}{\stackanchor{{Defender's}}{{action
$d$}}}}&123&0.7257&0.7257&0.9311&0.9311&0.6577&0.6577&0.7122&0.7122\\\
\cline{2-10}\cr&132&0.8900&0.9311&0.8900&0.9311&0.7122&0.7122&0.7122&0.7122\\\
\cline{2-10}\cr&213&0.5068&0.5068&0.9311&0.9311&0.4934&0.4934&0.7668&0.7668\\\
\cline{2-10}\cr&231&0.5068&0.5068&0.7668&0.9311&0.5068&0.5068&0.7668&0.9311\\\
\cline{2-10}\cr&312&0.7257&0.9311&0.7257&0.9311&0.7122&0.8766&0.7122&0.8766\\\
\cline{2-10}\cr&321&0.6712&0.7122&0.7257&0.9311&0.6712&0.7122&0.7257&0.9311\\\
\cline{2-10}\cr\end{array}$

Table 4: Payoff for each pure strategy profile of $3$-bit password scenario.

This strategy is part of an equilibrium and guarantees that for any choice of
the attacker the posterior Bayes vulnerability is at most $0.6573$ (so the
multiplicative leakage is bounded by $50\%$, an intermediate value between the
minimum of about $12\%$ and the maximum of about $112\%$).

The running time, on the other hand, of this new password-checker is the same
as that of the original one. Under the assumption that either the password, or
the low-input, are uniformly distributed, each check fails with probability
$\nicefrac{{1}}{{2}}$, giving a total expected time of $2(1-2^{-n})$. Hence
this technique substantially decreases the program’s information leakage,
without affecting at all its expected running time.

###  7.2 On optimal strategies for the defender

Interestingly, in the $3$-bit password case study from the previous section,
the defender’s optimal strategy consists in uniformly sampling among all
available versions of the checker. A uniform distribution seems to be an
adequate candidate for the defender, but is it always the best choice for any
prior and any number of bits?

We first answer this question in the case of a uniform prior $\pi$ for
arbitrary $n$-bit passwords, which already turns out to be challenging. Under
this prior, and exploiting a crucial symmetry of the password checker (see the
proof of Theorem 7.2), we can show that all strategies for the adversary are
in fact equivalent, namely

$\textit{U}(\alpha,\delta)=\textit{U}(\alpha^{\prime},\delta)\quad\text{for
all }\alpha,\alpha^{\prime},\delta\leavevmode\nobreak\ .$

For the defender, on the other hand, the situation is far from trivial:
although all _pure_ strategies $d$ are still equivalent,
$\textit{U}(\alpha,\delta)$ does in general depend on $\delta$. By exploiting
another symmetry of the password checker together with the symmetry of
$\mathbb{V}$, we can show that a uniform strategy is indeed optimal for the
defender, as stated in the following result.

[] Consider the password checker program of Algorithm 1 for $n$-bit passwords,
where the attacker controls the low input to the checker, and the defender
controls the order in which the bits are checked. If the prior $\pi$ on
possible passwords is uniform, and the payoff is given by the posterior Bayes-
vulnerability
$\textit{U}(\delta,\alpha)\allowbreak=\allowbreak\operatornamewithlimits{\displaystyle\mathbb{E}}_{\begin{subarray}{c}a\leftarrow\alpha\\\
\end{subarray}}\;\mathbb{V}\left[\pi,{{\osum_{d\leftarrow\delta}}}{C_{da}}\right]$,
then the strategy $(\delta^{*},\alpha)$ where $\delta^{*}$ is _uniform_ and
$\alpha$ is _arbitrary_ is an equilibrium strategy.

Perhaps surprisingly, however, Theorem 7.2 does not generalize to non-uniform
priors (or to different vulnerability metrics). More precisely, when the prior
on passwords is not uniform, the defender may benefit from assigning different
probabilities to different versions of the password checker. This subtlety
arises from the fact that the defender’s goal is not to maximize the
attacker’s uncertainty about the selected password checker itself (i.e., the
defender’s action), but it is rather to maximize the attacker’s uncertainty
about the secret value. The following examples illustrate this (perhaps
counter-intuitive) fact.

Consider again a $3$-bit password scenario, similar to that of the previous
section. Assume that the attacker knows only that the first bit of the
password is surely $0$, so that the prior on secrets is

$\pi^{(A)}=(0.25,0.25,0.25,0.25,0,0,0,0).$

The payoff table for this case is presented in Table 5(a), and a corresponding
equilibrium defender’s best strategy, computed using techniques from Alvim et
al. (2017), is

$\delta^{*(A)}=(0.25,0.25,0,0.25,0,0.25).$

Note that this equilibrium means that the defender never has to check the bits
in the order (2,1,3) or in the order (3,1,2). The game’s payoff (i.e.,
posterior Bayes vulnerability) in this case is $0.5625$, which is smaller than
the payoff of $0.5833$ that would ensue in case the defender’s strategy were
uniform. This means that, from the point of view of the defender, uniformly
randomizing is not optimal.

Now assume that the attacker knows that some passwords are more likely than
others, even if all are possible, as reflected in the prior

$\pi^{(B)}=(0.25,0.20,0.15,0.10,0.10,0.10,0.05,0.05).$

The payoff table for this case is presented in Table 5(b), and a corresponding
equilibrium defender’s best strategy can be computed to be

$\delta^{*(B)}=(0.1974,0.1974,0.1316,0.1316,0.1711,0.1711).$

Note that this equilibrium means that every version of the checker may be
selected by the defender, but the probability distribution is not uniform. The
game’s payoff (i.e., posterior Bayes vulnerability) in this case is $0.4553$,
which is again smaller than the payoff of $0.4666$ that would ensue in case
the defender’s strategy were uniform.

(a) Under prior $\pi^{(A)}$.

$\begin{array}[]{c|c||c|c|c|c|c|c|c|c|}\lx@intercol\hfil\hfil\lx@intercol&\lx@intercol\hfil\textbf{Attacker's
action $a$}\hfil\lx@intercol\\\
\cline{2-10}\cr&U(d,a)&000&001&010&011&100&101&110&111\\\
\cline{2-10}\cr\cline{2-10}\cr\hbox{\multirowsetup\rotatebox[origin={c}]{90.0}{\stackanchor{{Defender's}}{{action
$d$}}}}&123&0.75&0.75&0.75&0.75&0.25&0.25&0.25&0.25\\\
\cline{2-10}\cr&132&0.75&0.75&0.75&0.75&0.25&0.25&0.25&0.25\\\
\cline{2-10}\cr&213&0.75&0.75&0.75&0.75&0.50&0.50&0.50&0.50\\\
\cline{2-10}\cr&231&0.75&0.75&0.75&0.75&0.75&0.75&0.75&0.75\\\
\cline{2-10}\cr&312&0.75&0.75&0.75&0.75&0.50&0.50&0.50&0.50\\\
\cline{2-10}\cr&321&0.75&0.75&0.75&0.75&0.75&0.75&0.75&0.75\\\
\cline{2-10}\cr\end{array}$

(b) Under prior $\pi^{(B)}$.

$\begin{array}[]{c|c||c|c|c|c|c|c|c|c|}\lx@intercol\hfil\hfil\lx@intercol&\lx@intercol\hfil\textbf{Attacker's
action $a$}\hfil\lx@intercol\\\
\cline{2-10}\cr&U(d,a)&000&001&010&011&100&101&110&111\\\
\cline{2-10}\cr\cline{2-10}\cr\hbox{\multirowsetup\rotatebox[origin={c}]{90.0}{\stackanchor{{Defender's}}{{action
$d$}}}}&123&0.70&0.70&0.60&0.60&0.50&0.50&0.45&0.4\\\
\cline{2-10}\cr&132&0.70&0.65&0.70&0.65&0.50&0.50&0.50&0.5\\\
\cline{2-10}\cr&213&0.70&0.70&0.55&0.55&0.60&0.60&0.50&0.5\\\
\cline{2-10}\cr&231&0.70&0.70&0.55&0.55&0.70&0.70&0.55&0.5\\\
\cline{2-10}\cr&312&0.70&0.65&0.70&0.65&0.60&0.60&0.60&0.6\\\
\cline{2-10}\cr&321&0.70&0.65&0.65&0.60&0.70&0.65&0.65&0.6\\\
\cline{2-10}\cr\end{array}$

Table 5: Payoff tables, under different priors, for each pure strategy profile
of $3$-bit password scenario.

##  8 Related work

Many studies have applied game theory to analyses of security and privacy in
networks Basar (1983); Grossklags et al. (2008); Alpcan and Buchegger (2011),
cryptography Katz (2008), anonymity Acquisti et al. (2003), location privacy
Freudiger et al. (2009), and intrusion detection Zhu et al. (2009), to cite a
few. See Manshaei et al. (2013) for a survey.

In the context of quantitative information flow, most works consider only
passive attackers. Boreale and Pampaloni Boreale and Pampaloni (2015) consider
adaptive attackers, but not adaptive defenders, and show that in this case the
attacker’s optimal strategy can be always deterministic. Mardziel et al.
Mardziel et al. (2014) propose a model for both adaptive attackers and
defenders, but in none of their extensive case-studies the attacker needs a
probabilistic strategy to maximize leakage. In this paper we characterize when
randomization is necessary, for either attacker or defender, to achieve
optimality in our general information leakage games.

Security games have been employed to model and analyze payoffs between
interacting agents, especially between a defender and an attacker. Korzhyk et
al. Korzhyk et al. (2011) theoretically analyze security games and study the
relationships between Stackelberg and Nash Equilibria under various forms of
imperfect information. Khouzani and Malacaria Khouzani and Malacaria (2016)
study leakage properties when perfect secrecy is not achievable due to
constraints on the allowable size of the conflating sets, and provide
universally optimal strategies for a wide class of entropy measures, and for
$g$-entropies. In particular, they prove that designing a channel with minimum
leakage is equivalent to computing Nash equilibria in a corresponding two-
player zero-sum games of incomplete information for a range of entropy
measures. These works, contrarily to ours, do not consider games with hidden
choice, in which optimal strategies differ from traditional game-theory.

Several security games have modeled leakage when the sensitive information are
the defender’s choices themselves, rather than a system’s high input. For
instance, Alon et al. Alon et al. (2013) propose zero-sum games in which a
defender chooses probabilities of secrets and an attacker chooses and learns
some of the defender’s secrets. Then they present how the leakage on the
defender’s secrets gives influences on the defender’s optimal strategy. More
recently, Xu et al. Xu et al. (2015) show zero-sum games in which the attacker
obtains partial knowledge on the security resources that the defender
protects, and provide the defender’s optimal strategy under the attacker’s
such knowledge. Contrarily to these studies, in this paper we assume that a
secret value is drawn from some prior distribution and is not the defender’s
strategy itself.

Security games have also been used to provide optimal trade-offs between two
conflicting desirable properties. Khouzani et al. Khouzani et al. (2015) study
the clash between security and usability in the password selection, and
present a game-theoretic framework for determining an optimal trade-off. They
analyze guessing attacks and derive the optimal policies for secret picking as
Nash/Stackelberg Equilibria. Yang et al. Yang et al. (2012) propose a game-
theoretic framework to analyze user behavior in anonymity networks. They
consider the cost of anonymity in terms of the loss of utility. They also
consider incentives and their impact on users’ cooperation. Shokri et al.
Shokri et al. (2017) present a game-theoretic model for a designer to find the
optimal privacy mechanism by taking the adversary’s knowledge into account.
More specifically, they show a Stackelberg Bayesian game in which a user first
chooses a location obfuscation mechanism to maximize his location privacy and
then an adversary tries to estimate the user’s location to minimize its error.
In contrast, our work presents a more general framework that is not limited to
a particular domain, and focuses on protocol composition as a method to limit
the leakage.

Regarding channel operators, sequential and parallel composition of channels
have been studied (e.g., Kawamoto et al. (2017)), but we are unaware of any
explicit definition and investigation of hidden and visible choice operators.
Although Kawamoto et al. Kawamoto et al. (2016) implicitly use the hidden
choice to model a probabilistic system as the weighted sum of systems, they do
not derive the set of algebraic properties we do for this operator, and for
its interaction with the visible choice operator.

##  9 Conclusion and future work

In this paper we used protocol composition to model the introduction of noise
performed by the defender to prevent leakage of sensitive information. More
precisely, we formalized visible and hidden probabilistic choices of different
protocols. We then formalized the interplay between defender and attacker in a
game-theoretic framework adapted to the specific issues of QIF, where the
payoff is information leakage. We considered various kinds of leakage games,
depending on whether players act simultaneously or sequentially, and whether
the choices of the defender are visible or not to the attacker. We established
a hierarchy of these games, and provided methods for finding the optimal
strategies (at the points of equilibrium) in the various cases. We also proved
that in a sequential game with hidden choice, the behavioral strategies are
more advantageous for the defender than the mixed strategies. This contrast
with the standard game theory, where the two types of strategies are
equivalent.

As future research, we would like to extend leakage games to the case of
repeated observations, i.e., when the attacker can observe the outcomes of the
system in successive runs, under the assumption that both attacker and
defender may change the channel in each run. We would also like to extend our
framework to non zero-sum games, in which the costs of attack and defense are
not equivalent, and to analyze differentially-private mechanisms.

###### Acknowledgements.

The authors are thankful to Arman Khouzani and Pedro O. S. Vaz de Melo for
valuable discussions. This work was supported by JSPS and Inria under the
project LOGIS of the Japan-France AYAME Program, by the PEPS 2018 project
MAGIC, and by the project Epistemic Interactive Concurrency (EPIC) from the
STIC AmSud Program. Mário S. Alvim was supported by CNPq, CAPES, and FAPEMIG.
Yusuke Kawamoto was supported by JSPS KAKENHI Grant Number JP17K12667. All
authors contributed to the technical results, and are listed in alphabetical
order. The authors declare no conflict of interest. The following
abbreviations are used in this manuscript:
QIF | Quantitative information flow
---|---
yes multiple

##  Appendix A Proofs of Technical Results

In this section we provide the proofs of the technical results which are not
in the main body of the paper.

###  A.1 Preliminaries for proofs

We start by providing some necessary background for the subsequent technical
proofs.

Definition 4.3 states that two compatible channels (i.e., with the same input
space) are equivalent if yield the same value of vulnerability for every prior
and every vulnerability function. The result below, from the literature,
provides necessary and sufficient conditions for two channels being
equivalent. The result employs the extension of channels with an all-zero
column as follows. For any channel $C$ of type
$\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$, its _zero-column
extension_ $C^{0}$ is the channel of type
$\mathcal{X}\times\left(\mathcal{Y}\cup\\{y_{0}\\}\right)\rightarrow\mathbb{R}$,
with $y_{0}\notin\mathcal{Y}$, s.t. $C^{0}(x,y)=C(x,y)$ for all
$x\in\mathcal{X}$, $y\in\mathcal{Y}$, and $C^{0}(x,y_{0})=0$ for all
$x\in\mathcal{X}$.

[Characterization of channel equivalence Alvim et al. (2012); McIver et al.
(2014)] Two channels $C_{1}$ and $C_{2}$ are equivalent iff every column of
$C_{1}$ is a convex combination of columns of $C_{2}^{0}$, and every column of
$C_{2}$ is a convex combination of columns of $C_{1}^{0}$.

Note that the result above implies that for being equivalent, any two channels
must be compatible.

###  A.2 Proofs of Section 4

See 4.1

###### Proof.

Since hidden choice is defined as a summation of matrices, the type of
${\osum_{i\leftarrow\mu}}C_{i}$ is the same as the type of every $C_{i}$ in
the family.

To see that ${\osum_{i\leftarrow\mu}}C_{i}$ is a channel (i.e., all of its
entries are non-negative, and all of its rows sum up to 1), first note that,
since each $C_{i}$ in the family is a channel matrix, $C_{i}(x,y)$ lies in the
interval $[0,1]$ for all $x\in\mathcal{X}$, $y\in\mathcal{Y}$. Since $\mu$ is
a set of convex coefficients, from the definition of hidden choice it follows
that also $\sum_{i\in\mathcal{I}}\mu(i)C_{i}(x,y)$ must lie in the interval
$[0,1]$ for every $x,y$.

Second, note that for all $x\in\mathcal{X}$:

$\displaystyle\sum_{y\in\mathcal{Y}}\left({\osum_{i\leftarrow\mu}}C_{i}\right)(x,y)=$
$\displaystyle\,\sum_{y\in\mathcal{Y}}\sum_{i\in\mathcal{I}}\mu(i)C_{i}(x,y)$
(def. of hidden choice) $\displaystyle=$
$\displaystyle\,\sum_{i\in\mathcal{I}}\mu(i)\sum_{y\in\mathcal{Y}}C_{i}(x,y)$
$\displaystyle=$ $\displaystyle\,\sum_{i\in\mathcal{I}}\mu(i)\cdot 1$
($C_{i}{:}\mathcal{X}{\times}\mathcal{Y}{\rightarrow}\mathbb{R}$ are channels)
$\displaystyle=$ $\displaystyle\,1$ ($\mu$ is a prob. dist.)

∎

See 4.2

###### Proof.

Visible choice applied to a family $\\{C_{i}\\}$ of channels scales each
matrix $C_{i}$ by a factor $\mu(i)$, which preserves the type
$\mathcal{X}\times\mathcal{Y}_{i}\rightarrow\mathbb{R}$ of each matrix, and
then concatenates all the matrices so produced, yielding a result of type
$\mathcal{X}\times\left(\bigsqcup_{i\in\mathcal{I}}\mathcal{Y}_{i}\right)\rightarrow\mathbb{R}$.

To see that ${\bigsqcupdot_{i\leftarrow\mu}}C_{i}$ is a channel (i.e., that
all of its entries are non-negative, and that all rows sum-up to $1$), note
that each element of the visible choice on the family $\\{C_{i}\\}$ can be
denoted by $\left({\bigsqcupdot_{i\leftarrow\mu}}C_{i}\right)(x,(y,j))$, where
$x\in\mathcal{X}$, $j\in\mathcal{I}$, and $y\in\mathcal{Y}_{j}$. Then, note
that for all $x\in\mathcal{X}$, $j\in\mathcal{I}$, and $y\in\mathcal{Y}_{j}$:

$\displaystyle\left({\bigsqcupdot_{i\leftarrow\mu}}C_{i}\right)(x,(y,j))=$
$\displaystyle\,\left(\meddiamond_{i\in\mathcal{I}}\mu(i)C_{i}\right)(x,(y,j))$
(def. of visible choice) $\displaystyle=$
$\displaystyle\,\left(\mu(j)C_{j}\right)(x,y)$ (def. of concatenation)
$\displaystyle=$ $\displaystyle\,\mu(j)C_{j}(x,y)$ (def. of scalar mult.) (2)

which is a non-negative value, since, both $\mu(j)$ and $C_{j}(x,y)$ are non-
negative.

Finally, note that for all $x\in\mathcal{X}$:

$\displaystyle\sum_{\begin{subarray}{c}j\in\mathcal{I}\\\
y\in\mathcal{Y}_{j}\end{subarray}}\left({\bigsqcupdot_{i\leftarrow\mu}}C_{i}\right)(x,(y,j))=$
$\displaystyle\,\sum_{\begin{subarray}{c}j\in\mathcal{I}\\\
y\in\mathcal{Y}_{j}\end{subarray}}\mu(j)C_{j}(x,y)$ (by Eq. (A.2))
$\displaystyle=$
$\displaystyle\,\sum_{j\in\mathcal{I}}\mu(j)\sum_{y\in\mathcal{Y}_{j}}C_{j}(x,y)$
$\displaystyle=$ $\displaystyle\,\sum_{j\in\mathcal{I}}\mu(j)\cdot 1$
($C_{j}{:}\mathcal{X}{\times}\mathcal{Y}_{j}{\rightarrow}\mathbb{R}$ are
channels) $\displaystyle=$ $\displaystyle\,1$ ($\mu$ is a prob. dist.)

∎

See 4.3

###### Proof.

  1. a)

Idempotency of hidden choice:

$\displaystyle{\osum_{i\leftarrow\mu}}C_{i}=$
$\displaystyle\,\sum_{i}\mu(i)C_{i}$ (def. of hidden choice) $\displaystyle=$
$\displaystyle\,\sum_{i}\mu(i)C$ (since every $C_{i}=C$) $\displaystyle=$
$\displaystyle\,C\sum_{i}\mu(i)$ $\displaystyle=$ $\displaystyle\,C$ (since
$\mu$ is a prob. dist.)

  2. b)

Idempotency of visible choice:

$\displaystyle{\bigsqcupdot_{i\leftarrow\mu}}C_{i}=$
$\displaystyle\,\meddiamond_{i}\mu(i)C_{i}$ (def. of visible choice)
$\displaystyle=$ $\displaystyle\,\meddiamond_{i}\mu(i)C$ (since every
$C_{i}=C$) $\displaystyle\approx$ $\displaystyle\,C$ (by Lemma A.1)

In the above derivation, we can apply Lemma A.1 because every column of the
channel on each side of the equivalence can be written as a convex combination
of the zero-column extension of the channel on the other side.

∎

See 4.4

###### Proof.

  1. a)

$\displaystyle{\osum_{i\leftarrow\mu}}{\osum_{j\leftarrow\eta}}C_{ij}=$
$\displaystyle\,{\osum_{i\leftarrow\mu}}\left(\sum_{j}\eta(j)C_{ij}\right)$
(def. of hidden choice) $\displaystyle=$
$\displaystyle\,\sum_{i}\mu(i)\left(\sum_{j}\eta(j)C_{ij}\right)$ (def. of
hidden choice) $\displaystyle=$
$\displaystyle\,\sum_{i,j}\eta(i)\eta(j)C_{ij}$ (reorganizing the sums)
$\displaystyle=$ $\displaystyle\,{\osum_{\begin{subarray}{c}i\leftarrow\mu\\\
j\leftarrow\eta\end{subarray}}}C_{ij}$ (def. of hidden choice)

  2. b)

$\displaystyle{\bigsqcupdot_{i\leftarrow\mu}}{\bigsqcupdot_{j\leftarrow\eta}}C_{ij}=$
$\displaystyle\,{\bigsqcupdot_{i\leftarrow\mu}}\left(\meddiamond_{j}C_{ij}\right)$
(def. of visible choice) $\displaystyle=$
$\displaystyle\,\meddiamond_{i}\mu(i)\left(\meddiamond_{j}\eta(j)C_{ij}\right)$
(def. of visible choice) $\displaystyle\approx$
$\displaystyle\meddiamond_{ij}\mu(i)\eta(j)C_{ij}$ (by Lemma A.1)
$\displaystyle=$
$\displaystyle\,{\bigsqcupdot_{\begin{subarray}{c}i\leftarrow\mu\\\
j\leftarrow\eta\end{subarray}}}C_{ij}$ (def. of visible choice)

In the above derivation, we can apply Lemma A.1 because every column of the
channel on each side of the equivalence can be written as a convex combination
of the zero-column extension of the channel on the other side.

  3. c)

$\displaystyle{\osum_{i\leftarrow\mu}}{\bigsqcupdot_{j\leftarrow\eta}}C_{ij}=$
$\displaystyle\,{\osum_{i\leftarrow\mu}}\left(\meddiamond_{j}C_{ij}\right)$
(def. of visible choice) $\displaystyle=$
$\displaystyle\,\sum_{i}\mu(i)\left(\meddiamond_{j}\eta(j)C_{ij}\right)$ (def.
of hidden choice) $\displaystyle\approx$
$\displaystyle\,\meddiamond_{j}\eta(j)\left(\sum_{i}\eta(i)C_{ij}\right)$ (by
Lemma A.1) $\displaystyle=$
$\displaystyle\,{\bigsqcupdot_{j\leftarrow\eta}}{\osum_{i\leftarrow\mu}}C_{ij}$
(def. of operators)

In the above derivation, we can apply Lemma A.1 because every column of the
channel on each side of the equivalence can be written as a convex combination
of the zero-column extension of the channel on the other side.

∎

###  A.3 Proofs of Section 7

See 7.2

###### Proof.

We show that $(\delta^{*},\alpha)$ where $\delta^{*}$ is uniform and $\alpha$
is arbitrary, is a saddle point of $\textit{U}(\delta,\alpha)$. The proof will
rely on two crucial _symmetries_ of the password checker, in combination with
the use of a uniform prior. Note that, under uniform $\pi$, the Bayes-
vulnerability of a channel $C$ is proportional to the sum of the column maxima
of $C$, namely
$\mathbb{V}\left[\pi,C\right]=\frac{1}{|\mathcal{X}|}\sum_{y}\max_{x}C(x,y)$.
Given a permutation $\sigma$ of $\mathcal{X}$, define $C^{\sigma}$ as $C$ with
its rows permuted, namely $C^{\sigma}(x,y)=C(\sigma(x),y)$. Note that
$C^{\sigma}$ can be written as $M_{\sigma}C$ where $M_{\sigma}$ is a
permutation matrix. Permuting the rows does not affect the column maxima,
hence $\mathbb{V}\left[\pi,C\right]=\mathbb{V}\left[\pi,C^{\sigma}\right]$.

For the attacker things are simple, since we can show that under a uniform
$\pi$ all attacker strategies are equivalent, that is,

$\textit{U}(\alpha,\delta)=\textit{U}(\alpha^{\prime},\delta)\quad\text{for
all }\alpha,\alpha^{\prime},\delta\leavevmode\nobreak\ .$

To show this, we use the first important symmetry of the password checker,
which is due to the fact that the output of the algorithm only depends on
whether $x_{i}\neq a_{i}$ is true or false for each bit. Hence, any
modification on $a$ can be matched with a modification on $x$ that preserves
the output, namely for all $a,a^{\prime}$ there exists a permutation $\sigma$
of passwords such that $C_{da}=C_{da^{\prime}}^{\sigma}$ for all $d$. Denote
$C_{\delta a}={\osum_{d\leftarrow\delta}}C_{da}$, we have that

$C_{\delta
a}={\osum_{d\leftarrow\delta}}C_{da}={\osum_{d\leftarrow\delta}}M_{\sigma}C_{da^{\prime}}=M_{\sigma}{\osum_{d\leftarrow\delta}}C_{da^{\prime}}=C_{\delta
a^{\prime}}^{\sigma}$

From $\mathbb{V}\left[\pi,C_{\delta a}\right]=\mathbb{V}\left[\pi,C_{\delta
a^{\prime}}^{\sigma}\right]$ we have that
$\textit{U}(a,\delta)=\textit{U}(a^{\prime},\delta)$ for all pure strategies
$a,a^{\prime}$, which implies
$\textit{U}(\alpha,\delta)=\textit{U}(\alpha^{\prime},\delta)$ since
$\textit{U}(\alpha,\delta)$ is linear on $\alpha$. So in the remaining of the
proof we assume that the attacker plays the fixed pure strategy $a_{0}$,
having the zero bitstring $0..0$ as the low input.

For the defender, on the other hand, the situation is far from trivial:
although all _pure_ strategies $d$ are still equivalent,
$\textit{U}(\alpha,\delta)$ is _only convex_ on $\delta$ and as a consequence
the payoff highly depends on $\delta$. Our goal is to show that

$\textit{U}(a_{0},\delta)=\frac{1}{|\mathcal{X}|}\sum_{y}\max_{x}\sum_{d}\delta(d)C_{da_{0}}(x,y)$

is minimized on the uniform $\delta^{*}$. To do so, we show something
stronger, namely that _each addend_ of the $y$-sum is _simultaneously_
minimized on the uniform $\delta^{*}$. Fix an arbitrary $y$, and let

$f(\delta)=\max_{x}\delta\cdot\psi_{x}$

where $\cdot$ is the dot product and $\psi_{x}\in\mathbb{R}^{|\mathcal{D}|}$
is the vector defined by $\psi_{x}(d)=C_{da_{0}}(x,y)$. Note that, since
$C_{da_{0}}$ is deterministic, all elements of $\psi_{x}$ are either $0$ or
$1$. Intuitively, $\psi_{x}(d)=1$ if $x$ produces the fixed output $y$ when
the bit checking order is $d$.

We need to show that $f(\delta)$ is minimized on $\delta^{*}$. However, $f$
seen as a function on the whole $\mathbb{R}^{|\mathcal{D}|}$ has no global
minimum. In our case, though, $\delta$ is a probability distribution taking
values in $\mathbb{D}\mathcal{D}\subset\mathbb{R}^{|\mathcal{D}|}$. That is,
only $|\mathcal{D}|-1$ elements of $\delta$ are free, so we can reduce the
dimension by one as follows: fix some $d_{0}\in\mathcal{D}$ and let
$\tilde{\delta},\tilde{\psi}_{x}\in\mathbb{R}^{|\mathcal{D}|-1}$ be the same
as $\delta,\psi_{x}$ with the element corresponding to $d_{0}$ removed. We
have that $\delta(d_{0})=1-\sum_{d\neq
d_{0}}\delta(d)=1-\tilde{\delta}\cdot\mathbf{1}$, where $\mathbf{1}$ is the
“ones” vector, hence we can rewrite $f(\delta)$ as a function of
$\tilde{\delta}$:

$\displaystyle f(\tilde{\delta})$
$\displaystyle=\max_{x}\tilde{\delta}\cdot\tilde{\psi}_{x}+\delta(d_{0})\psi_{x}(d_{0})$
$\displaystyle=\max_{x}\tilde{\delta}\cdot\tilde{\psi}_{x}+(1-\tilde{\delta}\cdot\mathbf{1})\psi_{x}(d_{0})$
$\displaystyle=\max_{x}\tilde{\delta}\cdot(\tilde{\psi}_{x}-\psi_{x}(d_{0})\mathbf{1})+\psi_{x}(d_{0})$

So it is sufficient to show that $f(\tilde{\delta})$ is minimized on
$\tilde{\delta}^{*}$.

In the following, we use the fundamental concept of _subgradients_ from convex
analysis, which generalize gradients for non-differentiable functions. A
vector $v$ is a subgradient of a possibly non-differentiable convex function
$g:S\to\mathbb{R}$ at $x_{0}\in S$ iff

$g(x)-g(x_{0})\geq v\cdot(x-x_{0})\qquad\text{for all }x\in
S\leavevmode\nobreak\ .$

It is well-known that $g$ has a global minimum on $x_{0}$ iff the $\mathbf{0}$
vector belongs to the set of subgradients of $g$ at $x_{0}$ (this generalizes
the fact that differentiable convex functions have zero gradient on their
global minimum). Recall also that $g(x)=x\cdot v+c$ has a single subgradient
$v$, while for $g(x)=\max_{i}g_{i}(x)$, any subgradient of $g_{i}$ for _any
branch $i$_ giving the max, is also a subgradient of $g$. Finally, the set of
subgradients is convex, so any convex combination of them is also a
subgradient.

Hence, the subgradients of $f(\tilde{\delta})$ are
$\tilde{\psi}_{x}-\psi_{x}(d_{0})\mathbf{1}$, for any $x$ giving the maximum,
as well as their convex combinations. Our goal is to show that on
$\tilde{\delta}^{*}$ these include the zero vector.

We finally arrive to the second important symmetry of the password checker.
Let $\rho$ be a permutation of the set $\\{1,\ldots,n\\}$ of password bits.
Such a permutation could be seen both as a permutation on $\mathcal{X}$ (i.e.
$\rho(x)=x_{\rho(1)}..x_{\rho(n)}$; note that $\rho(x)$ has the same number of
$0$s and $1$s as $x$), as well as a permutation on $\mathcal{D}$ (a bit
checking order $d$ is _itself_ a permutation of bits, so we can set
$\rho(d)=\rho\circ d$). Since all low bits of $a_{0}$ are the same, applying
$\rho$ to both $x$ and $d$ does not change the outcome of the algorithm, that
is $C_{da_{0}}=C_{\rho(d)a_{0}}^{\rho}$.

Intuitively, if $d$ is selected uniformly, then the attacker cannot
distinguish $x$ from $\rho(x)$ since they produce the same output with the
same probability. More concretely, let $x\sim x^{\prime}$ denote that
$x^{\prime}=\rho(x)$ for some bit permutation $\rho$. Due to the
aforementioned symmetry we have that $\psi_{x}$ and $\psi_{x^{\prime}}$ have
the same number of $1$s which means that
$\delta^{*}\cdot\psi_{x}=\delta^{*}\cdot\psi_{x^{\prime}}$. Now, let
$x^{*}\in\mathrm{argmax}_{x}\delta^{*}\cdot\psi_{x}$. We have that _all_
$x\sim x^{*}$ also give the $\max$, hence all vectors

$\tilde{\psi}_{x}-\psi_{x}(d_{0})\mathbf{1}\qquad x\sim x^{*}$ (3)

are subgradients of $f$ on $\tilde{\delta}^{*}$. Finally, for any
$d,d^{\prime}$ there is a bit permutation $\rho$ such that
$d^{\prime}=\rho(d)$. Since $\psi_{x}(d)=\psi_{\rho(x)}(\rho(d))$ we have that
$(\sum_{x\sim x^{*}}\psi_{x})(d)=k$ (for some integer $k$) independently from
$d$. Hence, letting $c=|\\{x\ |\ x\sim x^{*}\\}|$ and averaging all
subgradients of (3) we get that

$\frac{1}{c}\sum_{x\sim
x^{*}}\big{(}\tilde{\psi}_{x}-\psi_{x}(d_{0})\mathbf{1}\big{)}=\frac{1}{c}(k\mathbf{1}-k\mathbf{1})=\mathbf{0}$

is also a subgradient, which concludes the proof. ∎

##  Appendix B Properties of binary versions of channel operators

In this section we derive some relevant properties of the binary versions of
the hidden and visible choice operators. We start with results regarding each
operator individually.

######  Proposition B.1 (Properties of the binary hidden choice).

For any channels $C_{1}$ and $C_{2}$ of the same type, and any values $0\leq
p,q\leq 1$, the binary hidden choice operator satisfies the following
properties:

  1. a)

_Idempotency_ : $C_{1}\;{{}_{p}{{{\oplus}}}}\;C_{1}=C_{1}$

  2. b)

_Commutativity_ :
$C_{1}\;{{}_{p}{{{\oplus}}}}\;C_{2}=C_{2}\;{{}_{\overline{p}}{{{\oplus}}}}\;C_{1}$

  3. c)

_Associativity_ :

$C_{1}\;{{}_{p}{{{\oplus}}}}\;(C_{2}\;{{}_{q}{{{\oplus}}}}\;C_{3})=(\nicefrac{{1}}{{q}}\cdot
C_{1}\;{{}_{p}{{{\oplus}}}}\;C_{2})\;{{}_{q}{{{\oplus}}}}\;\overline{p}\cdot
C_{3}$

if $q\neq 0$.

  4. d)

_Absorption_ :

$(C_{1}\;{{}_{p}{{{\oplus}}}}\;C_{2})\;{{}_{q}{{{\oplus}}}}\;(C_{1}\;{{}_{r}{{{\oplus}}}}\;C_{2})=C_{1}\;{{}_{(pq+\overline{q}r)}{{{\oplus}}}}\;C_{2}.$

###### Proof.

We will prove each property separately.

  1. a)

_Idempotency_ :

$\displaystyle C_{1}\;{{}_{p}{{{\oplus}}}}\;C_{1}=$ $\displaystyle\,p\cdot
C_{1}+\overline{p}\cdot C_{1}$ (def. of hidden choice) $\displaystyle=$
$\displaystyle\,(p+\overline{p})\cdot C_{1}$ $\displaystyle=$
$\displaystyle\,C_{1}$ ($p+\overline{p}=1$)

  2. b)

_Commutativity_ :

$\displaystyle C_{1}\;{{}_{p}{{{\oplus}}}}\;C_{2}=$ $\displaystyle\,p\cdot
C_{1}+\overline{p}\cdot C_{2}$ (def. of hidden choice) $\displaystyle=$
$\displaystyle\,\overline{p}\cdot C_{2}+p\cdot C_{1}$ $\displaystyle=$
$\displaystyle\,C_{2}\;{{}_{\overline{p}}{{{\oplus}}}}\;C_{1}$ (def. of hidden
choice)

  3. c)

_Associativity_ :

$\displaystyle\,C_{1}\;{{}_{p}{{{\oplus}}}}\;(C_{2}\;{{}_{q}{{{\oplus}}}}\;C_{3})$
$\displaystyle=$ $\displaystyle\,p\cdot C_{1}+\overline{p}(q\cdot
C_{2}+\overline{q}\cdot C_{3})$ (def. of hidden choice) $\displaystyle=$
$\displaystyle\,p\cdot C_{1}+\overline{p}q\cdot
C_{2}+\overline{p}\overline{q}\cdot C_{3}$ $\displaystyle=$
$\displaystyle\,q(p(\nicefrac{{1}}{{q}}\cdot C_{1})+\overline{p}\cdot
C_{2})+\overline{q}(\overline{p}\cdot C_{3})$ $\displaystyle=$
$\displaystyle\,(\nicefrac{{1}}{{q}}\cdot
C_{1}\;{{}_{p}{{{\oplus}}}}\;C_{2})\;{{}_{q}{{{\oplus}}}}\;\overline{p}\cdot
C_{3}$ (def. of hidden choice)

  4. d)

_Absorption_ : First note that:

$\displaystyle\,(C_{1}\;{{}_{p}{{{\oplus}}}}\;C_{2})\;{{}_{q}{{{\oplus}}}}\;(C_{1}\;{{}_{r}{{{\oplus}}}}\;C_{2})$
$\displaystyle=$
$\displaystyle\,q(pC_{1}+\overline{p}C_{2})+\overline{q}(rC_{1}+\overline{r}C_{2})$
(def. of hidden choice) $\displaystyle=$
$\displaystyle\,pqC_{1}+\overline{p}qC_{2}+\overline{q}rC_{1}+\overline{q}\overline{r}C_{2}$
$\displaystyle=$
$\displaystyle\,(pq+\overline{q}r)C_{1}+(\overline{p}q+\overline{q}\overline{r})C_{2}$
$\displaystyle=$
$\displaystyle\,C_{1}\;{{}_{(pq+\overline{q}r)}{{{\oplus}}}}\;C_{2}$ (*)

To complete the proof, note that in step (*) above, $pq+\overline{q}r$ and
$\overline{p}q+\overline{q}\overline{r}$ form a valid binary probability
distribution (they are both non-negative, and they add up to 1), then apply
the definition of hidden choice.

∎

######  Proposition B.2 (Properties of binary visible choice).

For any compatible channels $C_{1}$ and $C_{2}$, and any values $0\leq p,q\leq
1$, the visible choice operator satisfies the following properties:

  1. a)

_Idempotency_ : $C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;C_{1}\approx C_{1}$

  2. b)

_Commutativity_ : $C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;C_{2}\approx
C_{2}\;{{}_{\overline{p}}{{{\sqcupdot}}}}\;C_{1}$

  3. c)

_Associativity_ :
$C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;(C_{2}\;{{}_{q}{{{\sqcupdot}}}}\;C_{3})\approx(\nicefrac{{1}}{{q}}\cdot
C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;C_{2})\;{{}_{q}{{{\sqcupdot}}}}\;\overline{p}\cdot
C_{3}$ if $q\neq 0$.

###### Proof.

We will prove each property separately.

  1. a)

_Idempotency_ : $C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;C_{1}\approx C_{1}$, by
immediate application of Lemma A.1, since every column of the channel on each
side of the equivalence can be written as a convex combination of the zero-
column extension of the channel on the other side.

  2. b)

_Commutativity_ :

$\displaystyle C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;C_{2}=$ $\displaystyle\,p\cdot
C_{1}\diamond\overline{p}\cdot C_{2}$ (def. of visible choice)
$\displaystyle\approx$ $\displaystyle\ \overline{p}\cdot C_{2}\diamond p\cdot
C_{1}$ (by Lemma A.1) $\displaystyle=$ $\displaystyle\
C_{2}\;{{}_{\overline{p}}{{{\sqcupdot}}}}\;C_{1}$ (def. of visible choice).

In the above derivation, we can apply Lemma A.1 because every column of the
channel on each side of the equivalence can be written as a convex combination
of the zero-column extension of the channel on the other side.

  3. c)

_Associativity_ :

$\displaystyle
C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;(C_{2}\;{{}_{q}{{{\sqcupdot}}}}\;C_{3})=$
$\displaystyle\,p\cdot C_{1}\diamond\overline{p}(q\cdot
C_{2}\diamond\overline{q}\cdot C_{3})$ (def. of visible choice)
$\displaystyle\approx$ $\displaystyle\,p\cdot
C_{1}\diamond\left(\overline{p}q\cdot
C_{2}\diamond\overline{p}\overline{q}\cdot C_{3}\right)$ (by Lemma A.1)
$\displaystyle=$ $\displaystyle\,q(p(\nicefrac{{1}}{{q}}\cdot
C_{1})\diamond\overline{p}\cdot C_{2})\diamond\overline{q}(\overline{p}\cdot
C_{3})$ $\displaystyle=$ $\displaystyle\,(\nicefrac{{1}}{{q}}\cdot
C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;C_{2})\;{{}_{q}{{{\sqcupdot}}}}\;\overline{p}\cdot
C_{3}$ (def. of visible choice)

In the above derivation, we can apply Lemma A.1 because every column of the
channel on each side of the equivalence can be written as a convex combination
of the zero-column extension of the channel on the other side.

∎

Now we turn our attention to the interaction between hidden and visible choice
operators.

A first result is that hidden choice does not distribute over visible choice.
To see why, note that
$C_{1}\;{{}_{p}{{{\oplus}}}}\;(C_{2}\;{{}_{q}{{{\sqcupdot}}}}\;C_{3})$ and
$(C_{1}\;{{}_{p}{{{\oplus}}}}\;C_{2})\;{{}_{q}{{{\sqcupdot}}}}\;(C_{1}\;{{}_{p}{{{\oplus}}}}\;C_{3})$
cannot be both defined: if the former is defined, then $C_{1}$ must have the
same type as $C_{2}\;{{}_{q}{{{\sqcupdot}}}}\;C_{3}$, whereas if the latter is
defined, $C_{1}$ must have the same type as $C_{2}$, but
$C_{2}\;{{}_{q}{{{\sqcupdot}}}}\;C_{3}$ and $C_{2}$ do not have the same type
(they have different output sets).

However, as the next result shows, visible choice distributes over hidden
choice.

######  Proposition B.3 (Distributivity of $\;{{}_{p}{{{\sqcupdot}}}}\;$ over
$\;{{}_{q}{{{\oplus}}}}\;$).

Let $C_{1}$, $C_{2}$ and $C_{3}$ be compatible channels, and $C_{2}$ and
$C_{3}$ have the same type. Then, for any values $0\leq p,q\leq 1$:

$\displaystyle
C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;(C_{2}\;{{}_{q}{{{\oplus}}}}\;C_{3})\approx(C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;C_{2})\;{{}_{q}{{{\oplus}}}}\;(C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;C_{3}).$

###### Proof.

$\displaystyle\,C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;(C_{2}\;{{}_{q}{{{\oplus}}}}\;C_{3})$
$\displaystyle=$
$\displaystyle\,(C_{1}\;{{}_{q}{{{\oplus}}}}\;C_{1})\;{{}_{p}{{{\sqcupdot}}}}\;(C_{2}\;{{}_{q}{{{\oplus}}}}\;C_{3})$
(idempotency of visible choice) $\displaystyle=$ $\displaystyle\,p(q\cdot
C_{1}+\overline{q}\cdot C_{1})\diamond\overline{p}(q\cdot
C_{2}+\overline{q}\cdot C_{3})$ (def. of operators) $\displaystyle=$
$\displaystyle\,(pq\cdot C_{1}+p\overline{q}\cdot
C_{1})\diamond(\overline{p}q\cdot C_{2}+\overline{p}\overline{q}\cdot C_{3})$
$\displaystyle\approx$ $\displaystyle\,(pq\cdot
C_{1}\diamond\overline{p}q\cdot C_{2})+(p\overline{q}\cdot
C_{1}\diamond\overline{p}\overline{q}\cdot C_{3})$ (by Lemma A.1)
$\displaystyle=$ $\displaystyle\,q(p\cdot C_{1}\diamond\overline{p}\cdot
C_{2})+\overline{q}(p\cdot C_{1}\diamond\overline{p}\cdot C_{3})$
$\displaystyle=$
$\displaystyle\,q(C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;C_{2})+\overline{q}(C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;C_{3})$
(def. of visible choice) $\displaystyle=$
$\displaystyle\,(C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;C_{2})\;{{}_{q}{{{\oplus}}}}\;(C_{1}\;{{}_{p}{{{\sqcupdot}}}}\;C_{3})$
(def. of hidden choice)

In the above derivation, we can apply Lemma A.1 because every column of the
channel on each side of the equivalence can be written as a convex combination
of the zero-column extension of the channel on the other side. ∎

yes

## References

  * Sun et al. (2002) Sun, Q.; Simon, D.R.; Wang, Y.M.; Russell, W.; Padmanabhan, V.N.; Qiu, L.  Statistical identification of encrypted web browsing traffic.  Proc. of S&P. IEEE, 2002, pp. 19–30.
  * Dwork et al. (2006) Dwork, C.; Mcsherry, F.; Nissim, K.; Smith, A.  Calibrating noise to sensitivity in private data analysis.  Proc. of TCC. Springer, 2006, Vol. 3876, LNCS, pp. 265–284.
  * Chaum (1988) Chaum, D.  The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability.  Journal of Cryptology 1988, 1, 65–75.
  * Boreale and Pampaloni (2015) Boreale, M.; Pampaloni, F.  Quantitative information flow under generic leakage functions and adaptive adversaries.  Logical Methods in Computer Science 2015, 11.
  * Mardziel et al. (2014) Mardziel, P.; Alvim, M.S.; Hicks, M.W.; Clarkson, M.R.  Quantifying Information Flow for Dynamic Secrets.  Proc. of S&P, 2014, pp. 540–555.
  * Alvim et al. (2017) Alvim, M.S.; Chatzikokolakis, K.; Kawamoto, Y.; Palamidessi, C.  Information Leakage Games.  Proc. of GameSec. Springer, 2017, Vol. 10575, LNCS, pp. 437–457.
  * Rizzo and Duong (2012) Rizzo, J.; Duong, T.  The CRIME attack, 2012.
  * Alvim et al. (2016) Alvim, M.S.; Chatzikokolakis, K.; McIver, A.; Morgan, C.; Palamidessi, C.; Smith, G.  Axioms for Information Leakage.  Proc. of CSF, 2016, pp. 77–92.
  * Smith (2009) Smith, G.  On the Foundations of Quantitative Information Flow.  Proc. of FOSSACS. Springer, 2009, Vol. 5504, LNCS, pp. 288–302.
  * Chatzikokolakis et al. (2008) Chatzikokolakis, K.; Palamidessi, C.; Panangaden, P.  On the Bayes risk in information-hiding protocols.  J. of Comp. Security 2008, 16, 531–571.
  * Shannon (1948) Shannon, C.E.  A Mathematical Theory of Communication.  Bell System Technical Journal 1948, 27, 379–423, 625–56.
  * Massey (1994) Massey.  Guessing and Entropy.  Proceedings of the IEEE Int. Symposium on Information Theory. IEEE, 1994, p. 204.
  * Alvim et al. (2012) Alvim, M.S.; Chatzikokolakis, K.; Palamidessi, C.; Smith, G.  Measuring Information Leakage Using Generalized Gain Functions.  Proc. of CSF, 2012, pp. 265–279.
  * Alvim et al. (2018) Alvim, M.S.; Chatzikokolakis, K.; Kawamoto, Y.; Palamidessi, C.  Leakage and protocol composition in a game-theoretic perspective.  Proceedings of POST. Springer, 2018, LNCS.
  * Osborne and Rubinstein (1994) Osborne, M.J.; Rubinstein, A.  A Course in Game Theory; The MIT Press, 1994.
  * Braun et al. (2009) Braun, C.; Chatzikokolakis, K.; Palamidessi, C.  Quantitative Notions of Leakage for One-try Attacks.  Proc. of MFPS. Elsevier, 2009, Vol. 249, ENTCS, pp. 75–91.
  * McIver et al. (2014) McIver, A.; Morgan, C.; Smith, G.; Espinoza, B.; Meinicke, L.  Abstract Channels and Their Robust Information-Leakage Ordering.  Proc. of POST. Springer, 2014, Vol. 8414, LNCS, pp. 83–102.
  * Basar (1983) Basar, T.  The Gaussian test channel with an intelligent jammer.  IEEE Trans. Information Theory 1983, 29, 152–157.
  * Grossklags et al. (2008) Grossklags, J.; Christin, N.; Chuang, J.  Secure or Insure?: A Game-theoretic Analysis of Information Security Games.  Proc. of WWW, 2008, pp. 209–218.
  * Alpcan and Buchegger (2011) Alpcan, T.; Buchegger, S.  Security Games for Vehicular Networks.  IEEE Trans. Mob. Comput. 2011, 10, 280–290.
  * Katz (2008) Katz, J.  Bridging Game Theory and Cryptography: Recent Results and Future Directions.  Proc. of TCC, 2008, pp. 251–272.
  * Acquisti et al. (2003) Acquisti, A.; Dingledine, R.; Syverson, P.F.  On the Economics of Anonymity.  Proc. of FC, 2003, pp. 84–102.
  * Freudiger et al. (2009) Freudiger, J.; Manshaei, M.H.; Hubaux, J.P.; Parkes, D.C.  On Non-cooperative Location Privacy: A Game-theoretic Analysis.  Proc. of CCS, 2009, pp. 324–337.
  * Zhu et al. (2009) Zhu, Q.; Fung, C.J.; Boutaba, R.; Basar, T.  A game-theoretical approach to incentive design in collaborative intrusion detection networks.  Proc. of GAMENETS. IEEE, 2009, pp. 384–392.
  * Manshaei et al. (2013) Manshaei, M.H.; Zhu, Q.; Alpcan, T.; Bacşar, T.; Hubaux, J.P.  Game Theory Meets Network Security and Privacy.  ACM Comput. Surv. 2013, 45, 25:1–25:39.
  * Korzhyk et al. (2011) Korzhyk, D.; Yin, Z.; Kiekintveld, C.; Conitzer, V.; Tambe, M.  Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness.  J. Artif. Intell. Res. 2011, 41, 297–327.
  * Khouzani and Malacaria (2016) Khouzani, M.H.R.; Malacaria, P.  Relative Perfect Secrecy: Universally Optimal Strategies and Channel Design.  Proc. of CSF, 2016, pp. 61–76.
  * Alon et al. (2013) Alon, N.; Emek, Y.; Feldman, M.; Tennenholtz, M.  Adversarial Leakage in Games.  SIAM J. Discrete Math. 2013, 27, 363–385.
  * Xu et al. (2015) Xu, H.; Jiang, A.X.; Sinha, A.; Rabinovich, Z.; Dughmi, S.; Tambe, M.  Security Games with Information Leakage: Modeling and Computation.  Proc. of IJCAI, 2015, pp. 674–680.
  * Khouzani et al. (2015) Khouzani, M.H.R.; Mardziel, P.; Cid, C.; Srivatsa, M.  Picking vs. Guessing Secrets: A Game-Theoretic Analysis.  Proc. of CSF, 2015, pp. 243–257.
  * Yang et al. (2012) Yang, M.; Sassone, V.; Hamadou, S.  A Game-Theoretic Analysis of Cooperation in Anonymity Networks.  Proc. of POST, 2012, pp. 269–289.
  * Shokri et al. (2017) Shokri, R.; Theodorakopoulos, G.; Troncoso, C.  Privacy Games Along Location Traces: A Game-Theoretic Framework for Optimizing Location Privacy.  ACM Trans. Priv. Secur. 2017, 19, 11:1–11:31.
  * Kawamoto et al. (2017) Kawamoto, Y.; Chatzikokolakis, K.; Palamidessi, C.  On the Compositionality of Quantitative Information Flow.  Logical Methods in Computer Science 2017, 13, 1–31.
  * Kawamoto et al. (2016) Kawamoto, Y.; Biondi, F.; Legay, A.  Hybrid Statistical Estimation of Mutual Information for Quantifying Information Flow.  Proc. of FM 2016, 2016, pp. 406–425.


# THE VOLCSPEECH SYSTEM FOR THE ICASSP 2022 MULTI-CHANNEL MULTI-PARTY MEETING
TRANSCRIPTION CHALLENGE

###### Abstract

This paper describes our submission to ICASSP 2022 Multi-channel Multi-party
Meeting Transcription (M2MeT) Challenge. For Track 1, we propose several
approaches to empower the clustering-based speaker diarization system to
handle overlapped speech. Front-end dereverberation and the direction-of-
arrival (DOA) estimation are used to improve the accuracy of speaker
diarization. Multi-channel combination and overlap detection are applied to
reduce the missed speaker error. A modified DOVER-Lap is also proposed to fuse
the results of different systems. We achieve the final DER of 5.79% on the
Eval set and 7.23% on the Test set. For Track 2, we develop our system using
the Conformer model in a joint CTC-attention architecture. Serialized output
training is adopted to multi-speaker overlapped speech recognition. We propose
a neural front-end module to model multi-channel audio and train the model
end-to-end. Various data augmentation methods are utilized to mitigate over-
fitting in the multi-channel multi-speaker E2E system. Transformer language
model fusion is developed to achieve better performance. The final CER is
19.2% on the Eval set and 20.8% on the Test set.

Index Terms—  M2MeT, AliMeeting, speaker diarization, multi-channel multi-
speaker speech recognition, data augmentation

##  1 Introduction

Recently, multi-channel multi-party meeting transcription has attracted
increasing research interest. The speech-processing system is required to
handle the complex acoustic conditions in the meeting scenario. In this paper,
we introduce our speaker diarization and automatic speech recognition (ASR)
systems designed for the M2MeT challenge. Considering the clustering-based
speaker diarization is widely used in commercial applications, we explore
different approaches to improve the performance of the clustering-based system
for speech with a high speaker overlap ratio. For the ASR task, we propose
several approaches to improve the accuracy of the far-field multi-speaker
overlapping speech.

The organization of this paper is as follows. The details of our speaker
diarization system are introduced in Section 2. Section 3 describes our end-
to-end ASR system with the neural front-end and SOT. Section 4 concludes the
paper.

##  2 Track 1: Speaker Diarization

###  2.1 Data Preparation

Our speaker diarization system for Track 1 consists of several blocks. The
data description is as follows:

  * •

Front-end processing: The direction-of-arrival estimator is trained on the
multi-channel data simulated by the near-field recordings of AliMeeting Corpus
[1] with different room impulse responses (RIRs).

  * •

Speaker embedding: We use CN-Celeb [2, 3] as the training set. Also, the long
audio in AISHELL-4 [4] and AliMeeting is split into short segments. Each
segment only contains a single speaker and no overlap is included.

  * •

Clustering: The PLDA is trained using CN-Celeb. The training set of AliMeeting
is used as the development set to tune the parameters of VBx.

  * •

Overlap detection: The overlap detection models are trained on the same data
with the DOA estimator.

  * •

System fusion: The parameters used in the system fusion are tuned in the Eval
set of AliMeeting.

  * •

Data augmentation: MUSAN [5] and RIRs [6] are used in the training of the
speaker embedding extractors.

###  2.2 Detailed descriptions

####  2.2.1 Front-end Processing

Due to the high reverberation level in the distant speech communication
scenarios, we use a multi-channel dereverberation algorithm based on Kalman
filtering [7]. The method is implemented with a STFT using 25% overlapping 64
ms square-root Hann windows and a 1024-point FFT on 16 kHz sampled signals.
The dereverberation filter length is 10 for each frequency band.

The DOA of the sound source is proved to be helpful [8]. We train a neural-
net-based DOA estimator to obtain a 36-dim probability vector representing the
azimuth angles that divide the space with ten-degree intervals. We use four
2D-convolution blocks to extract frame-level features from the multi-channel
input and a max-pooling layer is employed after every convolution block. Four
layers of the DFSMN module [9] with a sigmoid function are implemented to
produce the posteriors of the DOA. In our experiments, the input is the
8-channel audio partitioned by 128 ms. The acoustic feature is 129-dim STFT
with a frame length of 16 ms and a frame shift of 8 ms.

####  2.2.2 Speaker Embedding

Two different architectures, ResNet-101 [10] and ECAPA-TDNN [11], are employed
as the speaker embedding extractor. The detailed structure about ResNet-101
can be found in [12]. A 3-fold speed augmentation is performed so each segment
is perturbed by 0.9 and 1.1 speed factors. This increases the number of
training speakers to 3. The Kaldi-based offline data augmentation is then
applied. We remove the babble noise since it contains human voice, which is
prohibited in this challenge. To train the ECAPA-TDNN network, the SpeechBrain
toolkit is used [13]. Online data augmentation is implemented in this case.
The babble noise is removed as well.

For both architectures, 80-dim log Mel filter-bank energies are used as the
input acoustic features. The frame size is 25 ms, and the frame shift is 10
ms.

####  2.2.3 Clustering

In the clustering stage, VBx [12] and spectral clustering are employed. For
VBx, the parameters are automatically tuned on the development set using the
Optuna toolkit [14]. For spectral clustering, we use an auto-tuning version
[15] so that the parameter is self-tuned. The clustering is performed on each
audio channel.

In our experiments, we find that combining the results from all 8-channels
improves the performance significantly. In the overlapped regions, different
speakers might be dominant in different channels due to the directional
microphone array, so the speakers could be recognized in different channels.
In this way, the combination reduces the missed speaker error. The algorithm
is shown in Alg. 1.

Algorithm 1 The combination of different diarization results

The diarization result $\boldsymbol{H}_{c}$ from channel $c=1,\ldots,8$, the
empty combination $\tilde{\boldsymbol{H}}=\phi$

Determine the number of speakers $N$ with majority voting.

for $c=1$ to 8 do

Skip this result if the number of speakers $N_{c}\neq N$.

if $\tilde{\boldsymbol{H}}=\phi$ then

$\tilde{\boldsymbol{H}}=\boldsymbol{H}_{c}$

else

Find the speaker label mapping:
$\boldsymbol{H}_{c}\rightarrow\tilde{\boldsymbol{H}}_{c}$ to minimize the
diarization error rate between $\tilde{\boldsymbol{H}}_{c}$ and
$\tilde{\boldsymbol{H}}$

$\tilde{\boldsymbol{H}}\leftarrow\tilde{\boldsymbol{H}}\cup\tilde{\boldsymbol{H}}_{c}$

end if

end for

We also explore the effectiveness of the azimuth information in speaker
diarization. More details will be released in the future.

An approach is proposed to integrate the DOA with the VBx framework. The main
differences of the proposed VBx are listed below.

  * •

State-specific distribution: We modify the state-specific distribution from
$p(\boldsymbol{x}_{t}|s)$ (Eq. (8) in [12]) to
$p(\boldsymbol{x}_{t}|s)p(\mathbf{d}_{t}|\mathbf{d}_{s})$, where $d_{t}$
denotes the DOA information at time $t$ and $d_{s}$ represents the DOA of
speaker $s$. After the initial AHC, the speaker-specific $d_{s}$ can be
computed by averaging the DOAs belonging to the same speaker. We assume
$p(\mathbf{d}_{t}|\mathbf{d}_{s})$ follows a simple Gaussian distribution
$N(\mathbf{d}_{t}|\mathbf{d}_{s},\sigma^{2}\mathbf{I})$, where $\sigma$ is a
tunable parameter. We set $\sigma=0.01$ in the experiment.

  * •

Transition probability: In the original VBx, the transition probability is
determined by $P_{loop}$. In our implementation, we represent the DOA
information by $a_{t}=\arg\max_{i}d_{t}(i)$, where $a_{t}$ denotes the most
possible speech direction. When $a_{t-1}\neq a_{t}$, it indicates a speaker
change. In this case, we set $p(s|s)=0.01$ and $p(s|s^{\prime})=0.99,\forall
s\neq s^{\prime}$. Otherwise, $p(s|s)=0.99$ and $p(s|s^{\prime})=0.01,\forall
s\neq s^{\prime}$. The probability is re-normalized per-state after the
assignment.

More details and results about the DOA-enhanced VBx will be released in the
future.

####  2.2.4 Overlap Detection

We train two overlap detection models. The first model (O1) consists of a
complex 2D-convolution [16] to handle spatial information, five separable
2D-convolution modules for feature extraction and two gated recurrent unit
(GRU) layers as the back-end. The second model (O2) consists of a complex
2D-convolution, a ResNet-based front-end and two Long short-term memory (LSTM)
layers as the back-end. The input is the 8-channel 129-dim STFT with a frame
length of 16 ms and a frame shift of 8 ms.

The frame-level posteriors of these two overlap detectors are averaged to
further improve the performance. The threshold for overlap decision is set to
0.5. A minimum silence duration of 300 ms and a minimum overlap duration of
100 ms are set to optimize the result in the development set.

Model | Precision | Recall | F1
---|---|---|---
O1 | 89.4% | 65.1% | 75.3%
O2 | 91.3% | 60.6% | 72.9%
Table 1: The results of the overlap detection on the Eval set of AliMeeting.

####  2.2.5 System Fusion

In DOVER-Lap [17], the number of speakers in the overlapped region is
determined by $\mathrm{round}(\sum_{s}w_{s})$, where $w_{s}$ is the voting
weight of speaker $s$. We find this operation often under-estimates the number
of speakers. In our modified DOVER-Lap, a speaker is recognized in the result
once the corresponding $w_{s}>0.5$. The voting weight is determined by a rank-
based fashion and no more tuning is needed.

###  2.3 Results

VBx System | Eval
---|---
DER(%) | JER(%)
Baseline | 15.24 | -
VBx (ours) | 13.89 | 26.17
\+ multi-channel | 8.93 | 18.68
\+ DRB | 8.35 | 18.00
\+ DOA est. | 7.80 | 17.49
\+ OVD | 6.76 | 16.70
\+ OVD fusion | 6.60 | 16.70
Table 2: The DER and JER of the VBx-based system. DRB denotes the front-end
dereverberation, and OVD denotes the overlap detection.

Table 2 shows the results of the VBx system with different configurations. The
window length is 1.44 s and the window shift is 0.72 s. The DER of the
official baseline is 15.24% while our VBx baseline achieves a DER of 13.89%.
By adding different methods proposed in this paper, the DER is reduced from
13.89% to 6.60% on the Eval set.

System | Eval | Test
---|---|---
DER(%) | JER(%) | DER(%)
Baseline | 15.24 | - | 15.6
1 VBx 1.44/0.72 | 6.60 | 16.70 | 8.02
2 VBx 1.44/0.24 | 6.44 | 16.45 | 7.74
3 VBx 0.96/0.24 | 6.80 | 16.65 | 8.15
4 ASC 1.44/0.72 | 7.55 | 17.21 | 8.41
5 ASC 1.44/0.24 | 7.00 | 16.62 | 8.22
6 SpeechBrain retrain | 7.83 | 17.90 | 10.83
DOVER-Lap 1+2+3 | 6.29 | 16.19 | 7.57
DOVER-Lap 1+2+3+4+5+6 | 6.09 | 15.97 | 7.34
Modified DOVER-Lap | 5.79 | 15.57 | 7.23

Table 3: The results of our systems with different configurations. ASC denotes
the auto-tuning spectral clustering.

Table 3 shows the performance of different systems based on VBx and spectral
clustering. Motivated by [18], systems with different time-scales are built.
We first fuse the VBx-based systems. The DER is improved from 6.44% to 6.29%.
Then, the spectral clustering is involved. The DER is further reduced to
6.09%. With the modified DOVER-Lap, our final submission achieves a DER of
5.79% on the Eval set and 7.23% on the Test set.

##  3 Track 2: Multi-Speaker ASR

###  3.1 Data Preparation

We train the ASR model on AliMeeting [1] and AISHELL-4 [4] dataset as
required. A simulated dataset generated from the near-field recordings in the
AliMeeting Corpus is also used for system robustness and generalization
ability. The single-channel near-field clips are convolved with RIRs simulated
by the image method to form the multi-channel counterpart. The T60
reverberation time ranges from 0.1 s to 1.5 s, and the room configuration is
randomly generated. In order to improve the generalization of the model to
overlapping speech, the number of speakers in a single clip is randomly
sampled from 1 to 4, and the overlap rate distribution is similar to which of
the AliMeeting corpus. The additive noise from MUSAN [5] and Freesound is also
convolved with simulated RIRs, which is added to the training data at an SNR
randomly sampled from 0dB to 30dB. We generate multiple copies of the data
under different mixing conditions to simulate enough combinations of clean
speech, background noise, and room configuration, resulting in a 600-hour
simulated dataset.

We have four datasets in total for the ASR system, as shown in Table 4. D1, D2
are training sets of AliMeeting far-field and near-field audio, respectively.
D3 is AISHELL-4 corpus that is recorded by a far-field microphone array. The
simulated dataset D4 has near-field recordings. All datasets have a 16k sample
rate.

Set | Training set
---|---
Hours | channel&sample rate | data
D1 | 105h | 8&16k | Train AliMeeting far
D2 | 105h | 1&16k | Train AliMeeting near
D3 | 120h | 8&16k | AISHELL-4
D4 | 600h | 8&16k | 8-channel simulation

Table 4: Data description for the ASR system.

###  3.2 System Description

Our ASR system is based on an encoder-decoder model with joint the CTC-
attention structure, and serialized output training (SOT) is adopted to
overlapping speech recognition. Furthermore, we use the neural front-end
speech enhancement module to model 8-channel audio, which joints training with
the base ASR model. Language model fusion is also used to improve performance.

####  3.2.1 E2E ASR Structure

Joint CTC-attention model [19, 20] is adopted to our ASR baseline model where
attention decoder and CTC (connectionist temporal classification) [21] block
receive the acoustic information from a shared encoder. The encoder is
composed of several layers of Conformer [22] blocks, and the decoder is
stacked with transformer blocks. To take the advantages of both CTC and
attention mechanisms, a multi-task learning (MTL) based loss function is
derived as [19],

$\mathcal{L}=\alpha\mathcal{L}_{CTC}+(1-\alpha)\mathcal{L}_{Attention}$ (1)

The weight $\alpha$ is a tunable parameter between 0 and 1.

During inference, the end-to-end speech recognition system combines the CTC
with attention probabilities in beam search process [19, 20]. The CTC
probabilities supply stable alignment for the attention model.

####  3.2.2 Multi-speaker Speech Recognition

Serialized output training (SOT) [23] is a widely used framework for multi-
speaker overlapping speech recognition, which sorts multi-speaker
transcriptions by start time one after another. SOT serializes multiple
references into a single token sequence, which has no limitation in the
maximum number of speakers and can model the dependencies among outputs for
different speakers. For example, in two-speaker case, the reference label will
be given as R = { $r_{1}^{1},\cdots,r_{N_{1}}^{1},\left\langle
sc\right\rangle,r_{1}^{2},r_{N_{2}}^{2},\left\langle eos\right\rangle$ } ,
which notes that $\left\langle eos\right\rangle$ is used at the end of the
sequence and the special symbol $\left\langle sc\right\rangle$ represents the
speaker change which is used to concatenate different utterances. This method
is also called the utterance-based first-in-first-out (FIFO) method.

####  3.2.3 Neural Front-end Speech Enhancement

It has been repeatedly reported that beamforming methods could produce
substantial improvements for ASR systems [24] in reverberant scenarios.
Recently, neural beamforming methods have drawn much attention since they have
the potential to learn and adapt from massive training data, which improves
their robustness to unknown positions and orientations of microphones and
sources, types of acoustic sources, and room geometry. Here, an end-to-end
multi-channel ASR system is adopted, bypassing above conventional beamforming
formalization. The front-end module architecture is shown in Figure 1. The
8-channel audio is first input into a Complex 2D-convolution layer, and a
complex linear layer [16] to fully exploit spectral and spatial information
between different input channels. Then, the power spectrum of each channel is
passed into two separable 2D-convolution blocks [25]. We use one self-
attention [20] layer for the feature of each channel. Then we concatenate the
8-channel features and use another self-attention layer with a sigmoid
function to obtain a mask combining the multi-channel spectral information.
Subsequently, the mask is implemented on the 8-channel STFT, and a sum
operation along the channel dimension is adopted to obtain a single channel
spectral feature. Finally, 80-dim Mel filter-bank energies are computed as
input features for the ASR back-end.

Fig. 1: Neural front-end speech enhancement module

####  3.2.4 Language Model

N-gram LM and transformer LM are adopted to our system to improve recognition
performance further. Near-field transcriptions and non-overlapping
transcriptions are used for language models training. Token-based units are
adopted to LM modeling. During inference, language models are combined with
shallow fusion. The process can formulate as

$\displaystyle\hat{Y}=$ $\displaystyle\text{argmax}_{Y\in y^{\ast}}\\{\alpha
P_{CTC}(Y|X)$ (2) $\displaystyle+(1-\alpha)P_{Attention}(Y|X)$
$\displaystyle+\beta P_{LM}(Y)\\}$

###  3.3 Results

####  3.3.1 End-to-End ASR training

We use the ESPnet toolkit [26] to build our system. We use 80-dimensional
filterbank (F-bank) features as the input feature, and frame length is 25 ms,
and frame shift is 10ms. The system label unit is Chinese characters and
English characters, including 3694 distinct units and three special symbols
that represent “unknown”, “null”, and “end of sentence” respectively.

The baseline single-channel ASR is a Conformer based AED (attention-based
encoder-decoder) model, which contains a 12-layer encoder and 6-layer decoder;
the self-attention and the feed-forward sub-layers have 256 and 2048 hidden
units. The head number of multi-head attention is set to 4 in all attention
sub-layers. The task weight $\alpha$ is empirically set to 0.3. Dropout rate
is set to 0.1, and SpecAugment [27] is applied to prevent over-fitting. We use
the adam optimizer. The whole network is trained for 100 epochs and warmup is
used for the first 25,000 iterations. The labels are sorted by utterance-based
FIFO, and it only uses the first channel as input.

The end-to-end multi-channel model has the same backbone as the single-channel
model, but with an additional front-end network which explains in section
3.2.3. The complex 2D-convolution has eight filters and a kernel size of
[5,5]. The complex linear layer has 257 hidden units. The single-channel self-
attention and multi-channel attention have 128 and 1024 hidden units,
respectively. During training multi-channel model, we apply global CMVN
(cepstral mean and variance normalization) on the output layer of front-end
module, which is calculated by all single-channel filterbank features.

####  3.3.2 Results and analysis

Table 5 shows the comparison of the single-channel model and multi-channel
model. Neural front-end joint training with ASR model has 20.5% and 20.3% CER
relative reduction for with and without simulation data respectively. We
divide the evaluation set into two parts, the overlapping and the non-
overlapping utterances. It is clearly observed that the neural front-end has a
significant gain in overlapping speech recognition, which learns the
contextual relationship within and across channels while modeling acoustic-to-
text mapping.

The effect of data augmentation is also shown in Table 5. We add 8-channel
simulation data for training, and the single-channel model has 13.5% CER
relative reduction, and the multi-channel model has 13.3% CER relative
reduction respectively. The result indicates that matching data simulation
methods benefit the model more.

ASR System | Eval
---|---
CER(%) | o-CER(%) | no-CER(%)
Baseline | 29.7 | - | -
Single-channel (D1+D2+D3) | 30.2 | 40.3 | 14.2
Single-channel (D1+D2+D3+D4) | 26.1 | 31.3 | 13.8
Multi-channel (D1+D3) | 24.0 | 30.7 | 13.5
Multi-channel (D1+D3+D4) | 20.8 | 25.9 | 12.0

Table 5: Comparison of single-channel model and multi-channel model. o-CER
means CER of overlapping utterances, and no-CER means CER of non-overlapping
utterances

Finally, we use model average and LM fusion to have further improvement. As
shown in Table 6, we average 20 lowest loss models, which achieves CER 6.7%
reduction relatively. We try N-gram LM and transformer LM fusion, but only
transformer LM with 0.1 interpolation parameter has 1% relative reduction.

ASR System | Eval | Test
---|---|---
CER(%) | CER(%)
Baseline | 29.7 | 30.9
\+ sim data & sp & rp | 24.0 | 25.1
\+ multi-channel model | 20.8 | 21.7
\+ model average | 19.4 | 20.9
\+ LM fusion | 19.2 | 20.8
Table 6: Comparison of effective methods to improve the ASR performance.

##  4 Conclusions

This paper describes the details of our systems built for the M2MeT challenge.
For Track 1, different efforts have been made to improve the clustering-based
system. Front-end dereverberation, multi-channel combination, clustering with
DOA information, overlap detection and the modified DOVER-Lap are presented.
For Track 2, a joint CTC-attention Conformer-based E2E network with serialized
output training is adopted to the multi-speaker ASR system. Neural front-end,
data augmentation, and different LMs are investigated to achieve the best
performance.

## References

  * [1] Fan Yu, Shiliang Zhang, Yihui Fu, Lei Xie, Siqi Zheng, Zhihao Du, Weilong Huang, Pengcheng Guo, Zhijie Yan, Bin Ma, et al.,  “M2met: The icassp 2022 multi-channel multi-party meeting transcription challenge,”  arXiv preprint arXiv:2110.07393, 2021.
  * [2] Yue Fan, Jiawen Kang, Lantian Li, Kaicheng Li, Haolin Chen, Sitong Cheng, Pengyuan Zhang, Ziya Zhou, Yunqi Cai, and Dong Wang,  “Cn-celeb: a challenging chinese speaker recognition dataset,” 2019\.
  * [3] Lantian Li, Ruiqi Liu, Jiawen Kang, Yue Fan, Hao Cui, Yunqi Cai, Ravichander Vipperla, Thomas Fang Zheng, and Dong Wang,  “CN-Celeb: multi-genre speaker recognition,”  Dec. 2020,  arXiv: 2012.12468.
  * [4] Yihui Fu, Luyao Cheng, Shubo Lv, Yukai Jv, Yuxiang Kong, Zhuo Chen, Yanxin Hu, Lei Xie, Jian Wu, Hui Bu, Xin Xu, Jun Du, and Jingdong Chen,  “AISHELL-4: An Open Source Dataset for Speech Enhancement, Separation, Recognition and Speaker Diarization in Conference Scenario,”  Aug. 2021,  arXiv: 2104.03603.
  * [5] David Snyder, Guoguo Chen, and Daniel Povey,  “Musan: A music, speech, and noise corpus,”  arXiv preprint arXiv:1510.08484, 2015.
  * [6] Tom Ko, Vijayaditya Peddinti, Daniel Povey, Michael L. Seltzer, and Sanjeev Khudanpur,  “A study on data augmentation of reverberant speech for robust speech recognition,”  in Proc. ICASSP, 2017, pp. 5220–5224.
  * [7] Sebastian Braun and Ivan Tashev,  “Low complexity online convolutional beamforming,”  in 2021 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA). IEEE, 2021, pp. 136–140.
  * [8] Siqi Zheng, Weilong Huang, Xianliang Wang, Hongbin Suo, Jinwei Feng, and Zhijie Yan,  “A real-time speaker diarization system based on spatial spectrum,”  in Proc. ICASSP. IEEE, 2021, pp. 7208–7212.
  * [9] Mengxiao Bi, Heng Lu, Shiliang Zhang, Ming Lei, and Zhijie Yan,  “Deep feed-forward sequential memory networks for speech synthesis,”  in Proc. ICASSP. IEEE, 2018, pp. 4794–4798.
  * [10] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
  * [11] Brecht Desplanques, Jenthe Thienpondt, and Kris Demuynck,  “Ecapa-tdnn: Emphasized channel attention, propagation and aggregation in tdnn based speaker verification,”  Proc. Interspeech, Oct 2020.
  * [12] Federico Landini, Ján Profant, Mireia Diez, and Lukáš Burget,  “Bayesian HMM clustering of x-vector sequences (VBx) in speaker diarization: theory, implementation and analysis on standard tasks,”  Dec. 2020,  arXiv: 2012.14952.
  * [13] Nauman Dawalatabad, Mirco Ravanelli, François Grondin, Jenthe Thienpondt, Brecht Desplanques, and Hwidong Na,  “ECAPA-TDNN Embeddings for Speaker Diarization,”  Apr. 2021,  arXiv: 2104.01466.
  * [14] Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama,  “Optuna: A next-generation hyperparameter optimization framework,”  in Proceedings of the 25rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019.
  * [15] Tae Jin Park, Kyu J. Han, Manoj Kumar, and Shrikanth Narayanan,  “Auto-Tuning Spectral Clustering for Speaker Diarization Using Normalized Maximum Eigengap,”  IEEE Signal Processing Letters, vol. 27, pp. 381–385, 2020.
  * [16] Yanxin Hu, Yun Liu, Shubo Lv, Mengtao Xing, Shimin Zhang, Yihui Fu, Jian Wu, Bihong Zhang, and Lei Xie,  “DCCRN: Deep complex convolution recurrent network for phase-aware speech enhancement,”  in Proc. INTERSPEECH. ISCA, 2021, pp. 2472–2476.
  * [17] Desh Raj, Leibny Paola Garcia-Perera, Zili Huang, Shinji Watanabe, Daniel Povey, Andreas Stolcke, and Sanjeev Khudanpur,  “DOVER-Lap: A Method for Combining Overlap-aware Diarization Outputs,”  Nov. 2020,  arXiv: 2011.01997.
  * [18] Keke Wang, Xudong Mao, Hao Wu, Chen Ding, Chuxiang Shang, Rui Xia, and Yuxuan Wang,  “The bytedance speaker diarization system for the voxceleb speaker recognition challenge 2021,”  arXiv preprint arXiv:2109.02047, 2021.
  * [19] Suyoun Kim, Takaaki Hori, and Shinji Watanabe,  “Joint ctc-attention based end-to-end speech recognition using multi-task learning,”  in Proc. ICASSP. IEEE, 2017, pp. 4835–4839.
  * [20] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin,  “Attention is all you need,”  in Advances in neural information processing systems, 2017, pp. 5998–6008.
  * [21] Alex Graves, Santiago Fernández, Faustino Gomez, and Jürgen Schmidhuber,  “Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks,”  in Proceedings of the 23rd international conference on Machine learning, 2006, pp. 369–376.
  * [22] Anmol Gulati et al.,  “Conformer: Convolution-augmented transformer for speech recognition,”  in Proc. INTERSPEECH. ISCA, 2020, pp. 5036–5040.
  * [23] Naoyuki Kanda, Yashesh Gaur, Xiaofei Wang, Zhong Meng, and Takuya Yoshioka,  “Serialized output training for end-to-end overlapped speech recognition,”  in Proc. INTERSPEECH. ISCA, 2020, pp. 2797–2801.
  * [24] Matthias Wölfel and John McDonough,  Distant speech recognition,  John Wiley & Sons, 2009.
  * [25] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam,  “Mobilenets: Efficient convolutional neural networks for mobile vision applications,”  arXiv preprint arXiv:1704.04861, 2017.
  * [26] Shinji Watanabe, Takaaki Hori, Shigeki Karita, Tomoki Hayashi, Jiro Nishitoba, Yuya Unno, Nelson Enrique Yalta Soplin, Jahn Heymann, Matthew Wiesner, Nanxin Chen, et al.,  “ESPnet: End-to-end speech processing toolkit,”  in arXiv preprint arXiv:1804.00015, 2018.
  * [27] Daniel S Park, William Chan, Yu Zhang, Chung-Cheng Chiu, Barret Zoph, Ekin D Cubuk, and Quoc V Le,  “Specaugment: A simple data augmentation method for automatic speech recognition,”  arXiv preprint arXiv:1904.08779, 2019.