# Neyman-Pearson lemma for Bayes factors

Andrew<EMAIL_ADDRESS>[ Department of Physics
and Institute of Theoretical Physics, Nanjing Normal University, Nanjing,
Jiangsu 210023, China<EMAIL_ADDRESS>
(0000)

###### Abstract

We point out that the Neyman-Pearson lemma applies to Bayes factors if we
consider _expected_ type-1 and type-2 error rates. That is, the Bayes factor
is the test statistic that maximises the expected power for a fixed expected
type-1 error rate. For Bayes factors involving a simple null hypothesis, the
expected type-1 error rate is just the completely frequentist type-1 error
rate. Lastly we remark on connections between the Karlin-Rubin theorem and
uniformly most powerful tests, and Bayes factors. This provides frequentist
motivations for computing the Bayes factor and could help reconcile Bayesians
and frequentists.

###### doi:

0000

††volume: 00††issue: 0

##  1 Introduction

Testing models and hypotheses against experimental data is a fundamental part
of science yet the statistical approaches for doing it remain contentious. In
many fields null hypothesis significance testing via p-values is popular. In
this approach, one tests a particular null hypothesis by computing the
probability of obtaining data as or more extreme than that observed, assuming
that the null hypothesis were true. This probability, the p-value, may be used
as either a measure of evidence against the null hypothesis, or as a means to
controlling a type-1 error rate (Neyman, 1977). This error rate is the rate at
which we would reject the null hypothesis when it was true. If we reject the
null hypothesis only when $p<\alpha$, the type-1 error rate would be $\alpha$.

The use of p-values has been contentious for decades (Edwards et al., 1963),
and in the recent years the situation appeared to reach a critical point
(Benjamin et al., 2018; Lakens et al., 2018), after it became apparent that
many effects discovered through null hypothesis significance testing were in
fact spurious and could not be reproduced by other researchers (Ioannidis,
2005). All kinds of remedies have been proposed, from abandoning null
hypothesis significance testing altogether (McShane et al., 2019) through to
Bayesian methods, including Bayes factors (Jeffreys, 1939; Kass and Raftery,
1995).

In the Bayesian approach we compute directly the relative probability that two
models, $H_{0}$ and $H_{1}$, predict the observed data, $\mathcal{D}$,

$B(\mathcal{D})\equiv\frac{p\mathopen{}\left(\mathcal{D}\,\middle|\,H_{1}\right)\mathclose{}}{p\mathopen{}\left(\mathcal{D}\,\middle|\,H_{0}\right)\mathclose{}}.$
(1.1)

This so-called Bayes factor updates the relative plausibility of two models.
The numerator and denominator in the Bayes factor are Bayesian evidences. In
general for composite models they may be written

$p\mathopen{}\left(\mathcal{D}\,\middle|\,H\right)\mathclose{}=\int
p\mathopen{}\left(\mathcal{D}\,\middle|\,H,\boldsymbol{\theta}\right)\mathclose{}p\mathopen{}\left(\boldsymbol{\theta}\,\middle|\,H\right)\mathclose{}\,\text{d}^{n}\theta,$
(1.2)

that is, as the marginal likelihood, where $\boldsymbol{\theta}$ are the
model’s $n$ unknown parameters with prior density
$p\mathopen{}\left(\boldsymbol{\theta}\,\middle|\,H\right)\mathclose{}$.

In the null hypothesis significance test, we are left to decide what possible
data would be more extreme than that observed. If we consider a fixed type-1
error rate, this amounts to choosing a rejection region, $\mathcal{R}$, in the
sample space of the experiment of size $\alpha$. Although other points of view
exist, the dominant approach is choosing a rejection region that maximises the
chance of rejecting the null hypothesis when it is false, i.e., maximising the
power, $1-\beta$. In other words, we chose $\mathcal{R}$ such that for fixed

$\alpha\equiv
P\mathopen{}\left(\mathcal{R}\,\middle|\,H_{0}\right)\mathclose{}$ (1.3)

we maximise

$1-\beta\equiv
P\mathopen{}\left(\mathcal{R}\,\middle|\,H_{1}\right)\mathclose{}.$ (1.4)

Equivalently, we minimise the type-2 error rate $\beta$, the probability of
not rejecting the null hypothesis when it is false. The Neyman-Pearson lemma
(Neyman et al., 1933) and the Karlin-Rubin theorem (Casella and Berger, 2002)
indicate the most powerful tests are often built upon likelihood ratios, and
likelihood ratios are ubiquitous in significance tests.

We could, on the other hand, relinquish control of the type-1 error rate, but
insist on a rejection region that minimises a weighted sum of type-1 and
type-2 error rates (Lindley, 1953; Lehmann, 1958; Savage, 1961; Mudge et al.,
2012),

$W\equiv w_{1}\alpha+w_{2}\beta,$ (1.5)

with weights $w_{1}$ and $w_{2}$. For the purposes of the calculations and
arguments in this work, this is equivalent to the conventional approach
discussed above. To see that, suppose that the region that minimises eq. 1.5
has size $\alpha^{\prime}$. Since this region minimises $W$, among all
possible regions of size $\alpha^{\prime}$, it must be the one that maximises
the power, $1-\beta$.

In this work, we use the Bayes factor as a test statistic in a frequentist
setting, argue that it is an optimal choice and that this may help reconcile
advocates of Bayesian and frequentist procedures for hypothesis testing. The
idea of using the Bayes factor in this way and its potential for harmonising
Bayesian and frequentist procedures (Berger, 2003; Bayarri et al., 2016) dates
as far back as the 1950s (Good, 1957, 1961, 1992), though Berger et al. (1997)
notes that it failed to gain traction among practitioners. In sec. 2 we
briefly review the Neyman-Pearson lemma and the Karlin-Rubin theorem, and in
sec. 3 and sec. 4, we show they may be applied to Bayes factors, such that the
Bayes factor is the most powerful choice of test statistic. This was
previously discussed formally in Zhang (2017). Besides drawing attention to
the relevant results and presenting them in an original, pedagogical manner,
we combine the ideas of Good (1957, 1961, 1992) and results of Zhang (2017).
We thus argue in sec. 5 that the Neyman-Pearson lemma and Karlin-Rubin theorem
in fact put Bayes factors at the centre of frequentist hypothesis tests as
they are an optimal choice of test statistic. This may help finally reconcile
Bayesian and frequentist approaches to testing.

##  2 The Neyman-Pearson lemma

For simple hypotheses with no unknown parameters, the Neyman-Pearson lemma
(Neyman et al., 1933) tell us that the likelihood ratio,

$\lambda(\mathcal{D})=\frac{p\mathopen{}\left(\mathcal{D}\,\middle|\,H_{1}\right)\mathclose{}}{p\mathopen{}\left(\mathcal{D}\,\middle|\,H_{0}\right)\mathclose{}},$
(2.1)

is an optimal test statistic. The rejection region of size $\alpha$ that
maximises the power must be a contour of the likelihood ratio,
$\mathcal{R}=\left\\{\mathcal{D}:\,\lambda(\mathcal{D})\geq\lambda_{0}\right\\}$,
where the value at the contour, $\lambda_{0}$, depends on the desired type-1
error rate and would be found from eq. 1.3. The Neyman-Pearson lemma doesn’t
extend to composite hypotheses that depend on unknown parameters, as the
optimal choice of test statistic would in general depend on the assumed values
for the unknown parameters. In some cases, a uniformly most powerful test
(UMPT) exists, which maximises the power for any values of the unknown
parameters in the alternative hypothesis. The Karlin-Rubin theorem
demonstrates cases in which a UMPT exists; see sec. 4.

##  3 The Neyman-Pearson lemma for Bayes factors

In the Bayesian formalism, for any composite model, we may find a simple model
by marginalising the $n$ unknown parameters,

$p\mathopen{}\left(\mathcal{D}\,\middle|\,H\right)\mathclose{}=\int
p\mathopen{}\left(\mathcal{D}\,\middle|\,H,\boldsymbol{\theta}\right)\mathclose{}p\mathopen{}\left(\boldsymbol{\theta}\,\middle|\,H\right)\mathclose{}\,\text{d}^{n}\theta.$
(3.1)

This is the prior predictive for the data and when evaluated at the observed
data, the Bayesian evidence for the model. We may thus use our Bayes factor in
place of the likelihood ratio in the Neyman-Pearson lemma. In this case,
though, the error rates are subtly re-interpreted, and to distinguish them we
denote them with a bar,

$\displaystyle\bar{\alpha}$ $\displaystyle\equiv
P\mathopen{}\left(\mathcal{R}\,\middle|\,H_{0}\right)\mathclose{}=\int
P\mathopen{}\left(\mathcal{R}\,\middle|\,H_{0},\boldsymbol{\theta}_{0}\right)\mathclose{}\,p\mathopen{}\left(\boldsymbol{\theta}_{0}\,\middle|\,H_{0}\right)\mathclose{}\,\text{d}^{n}\theta_{0}$
(3.2) $\displaystyle 1-\bar{\beta}$ $\displaystyle\equiv
P\mathopen{}\left(\mathcal{R}\,\middle|\,H_{1}\right)\mathclose{}=\int
P\mathopen{}\left(\mathcal{R}\,\middle|\,H_{1},\boldsymbol{\theta}_{1}\right)\mathclose{}\,p\mathopen{}\left(\boldsymbol{\theta}_{1}\,\middle|\,H_{1}\right)\mathclose{}\,\text{d}^{m}\theta_{1}$
(3.3)

That is, here they are the _expected_ error rates, averaging over the possible
values for the $n$ unknown model parameters $\boldsymbol{\theta}_{0}$ in the
null hypothesis and for the $m$ unknown model parameters
$\boldsymbol{\theta}_{1}$ in the alternative hypothesis. They do not in
general correspond to any observable long-run error rates.

This requires, of course, choices of prior density,
$p\mathopen{}\left(\boldsymbol{\theta}_{0}\,\middle|\,H_{0}\right)\mathclose{}$
and
$p\mathopen{}\left(\boldsymbol{\theta}_{1}\,\middle|\,H_{1}\right)\mathclose{}$;
see e.g., Kass and Wasserman (1996); Consonni et al. (2018) for discussion of
rules for choosing priors in a Bayesian setting. In a frequentist setting, the
priors needn’t be interpreted in the same manner as in subjective or objective
Bayesian approaches. The prior for any parameters in the alternative
hypothesis,
$p\mathopen{}\left(\boldsymbol{\theta}_{1}\,\middle|\,H_{1}\right)\mathclose{}$,
may be thought of as a weight function that indicates which choices of
parameters we want our test to be most powerful for (Good and Crook, 1974;
Bayarri et al., 2016). Similarly, the prior for any parameters in a composite
null hypothesis,
$p\mathopen{}\left(\boldsymbol{\theta}_{0}\,\middle|\,H_{0}\right)\mathclose{}$,
weights which choices of parameters we most want to control the type-1 error
rate for.

We could instead consider a fixed _maximum_ type-1 error rate, $\hat{\alpha}$,
for any values of the unknown parameters in the null hypothesis. If we assume
that it occurs when $\boldsymbol{\theta}_{0}=\hat{\boldsymbol{\theta}}_{0}$,
we may write

$\hat{\alpha}=P\mathopen{}\left(\mathcal{R}\,\middle|\,H_{0},\hat{\boldsymbol{\theta}}_{0}\right)\mathclose{}.$
(3.4)

This is in fact equivalent to a sharp prior
$p\mathopen{}\left(\boldsymbol{\theta}_{0}\,\middle|\,H_{0}\right)\mathclose{}=\delta(\boldsymbol{\theta}_{0}-\hat{\boldsymbol{\theta}}_{0})$,
i.e., specifying through our prior that we must control the type-1 error rate
for the parameters that maximise the type-1 error rate. In this case we would
use the Bayes factor,

$B(\mathcal{D})=\frac{\int
p\mathopen{}\left(\mathcal{D}\,\middle|\,H_{1},\boldsymbol{\theta}_{1}\right)\mathclose{}\,p\mathopen{}\left(\boldsymbol{\theta}_{1}\,\middle|\,H_{1}\right)\mathclose{}\,\text{d}^{n}\theta_{1}}{p\mathopen{}\left(\mathcal{D}\,\middle|\,H_{0},\hat{\boldsymbol{\theta}}_{0}\right)\mathclose{}}$
(3.5)

in place of the likelihood ratio in the Neyman-Pearson lemma. Under the null
hypothesis the expected magnitude of the preference for the alternative model
from the Bayes factor in eq. 1.1 must be smaller than that from the one used
when we control the maximum type-1 error rate in eq. 3.5. This result follows
from Gibbs’ inequality,

$\int\left[\log\left(\frac{p\mathopen{}\left(\mathcal{D}\,\middle|\,H_{1}\right)\mathclose{}}{p\mathopen{}\left(\mathcal{D}\,\middle|\,H_{0}\vphantom{,\hat{\boldsymbol{\theta}}_{0}}\right)\mathclose{}}\right)-\log\left(\frac{p\mathopen{}\left(\mathcal{D}\,\middle|\,H_{1}\right)\mathclose{}}{p\mathopen{}\left(\mathcal{D}\,\middle|\,H_{0},\hat{\boldsymbol{\theta}}_{0}\right)\mathclose{}}\right)\right]\,p\mathopen{}\left(\mathcal{D}\,\middle|\,H_{0}\right)\mathclose{}\,\text{d}\mathcal{D}\leq
0.$ (3.6)

So whilst controlling the maximum error rate rather than the expected error
may seem conservative, the computation involves the Bayes factor in eq. 3.5
that we expect to overstate the evidence against the null hypothesis.

If the null hypothesis is simple, as is often the case,
$\bar{\alpha}=\hat{\alpha}=\alpha$, and so the type-1 error rates may be
interpreted in the usual, completely frequentist manner. The power, on the
other hand, remains the expected power, averaged across the unknown parameters
in the alternative hypothesis.

##  4 Karlin-Rubin theorem for Bayes factors

It would be desirable to extend the Neyman-Pearson lemma to composite models.
Unfortunately, UMPT do not always exist as the optimal test generally depends
on the values of the unknown parameters in the alternative hypothesis. There
are approaches that sidestep the issue such as a minimax treatment of type-1
error rates and power. The Karlin-Rubin theorem (Casella and Berger, 2002), on
the other hand, extends the Neyman-Pearson lemma to a UMPT in a composite case
in special circumstances.

To apply the theorem, the null and alternative hypothesis must be disjoint
regions of a one-dimensional parameter space separated by a boundary at
$\theta_{C}$, that is,

$H_{0}:\,\theta\leq\theta_{C}\quad\text{and}\quad H_{1}:\,\theta>\theta_{C}.$
(4.1)

Suppose that a sufficient test statistic, $T$, exists and that the likelihood
ratio

$\lambda(T;\theta,\theta^{\prime})=\frac{p\mathopen{}\left(T\,\middle|\,\theta\right)\mathclose{}}{p\mathopen{}\left(T\,\middle|\,\theta^{\prime}\right)\mathclose{}}$
(4.2)

is a monotonic non-decreasing function of $T$ for any
$\theta>\theta^{\prime}$. We call these condition the monotone likelihood
ratio (MLR) conditions. Under these conditions, the UMPT is a threshold on
$T$, $\mathcal{R}=\left\\{T:\,T\geq T_{0}\right\\}$. The threshold $T_{0}$ is
determined by fixing the maximum type-1 error rate,

$\hat{\alpha}=P\mathopen{}\left(\mathcal{R}\,\middle|\,H_{0},\theta_{C}\right)\mathclose{}$
(4.3)

and occurs when $\theta=\theta_{C}$. This ensures the size of the test is no
larger than $\hat{\alpha}$ for any choice of unknown parameter in the null
hypothesis.

We can make a similar statement for our Bayes factor,

$B(T)=\frac{p\mathopen{}\left(T\,\middle|\,H_{1}\right)\mathclose{}}{p\mathopen{}\left(T\,\middle|\,H_{0}\right)\mathclose{}}=\frac{\int
p\mathopen{}\left(T\,\middle|\,H_{1},\boldsymbol{\theta}_{1}\right)\mathclose{}\,p\mathopen{}\left(\boldsymbol{\theta}_{1}\,\middle|\,H_{1}\right)\mathclose{}\,\text{d}^{m}\theta_{1}}{\int
p\mathopen{}\left(T\,\middle|\,H_{0},\boldsymbol{\theta}_{0}\right)\mathclose{}\,p\mathopen{}\left(\boldsymbol{\theta}_{0}\,\middle|\,H_{0}\right)\mathclose{}\,\text{d}^{n}\theta_{0}.}$
(4.4)

We assume that the prior
$p\mathopen{}\left(\boldsymbol{\theta}_{0}\,\middle|\,H_{0}\right)\mathclose{}$
for the unknown parameters in the null hypothesis was chosen. We suppose that,
with that choice, the Bayes factor is always a monotonic function of $T$ for
any choice of prior for the $m$ unknown parameters in the alternative model,
$p\mathopen{}\left(\boldsymbol{\theta}_{1}\,\middle|\,H_{1}\right)\mathclose{}$.
This is satisfied by the MLR conditions of the Karlin-Rubin theorem for any
choice of
$p\mathopen{}\left(\boldsymbol{\theta}_{0}\,\middle|\,H_{0}\right)\mathclose{}$;
see App. A. The Karlin-Rubin theorem considered a fixed maximum type-1 error
rate, $\hat{\alpha}$. In our Bayesian interpretation, we could fix this or the
mean error rate $\bar{\alpha}$. If we fix the former, we consider the Bayes
factor in eq. 3.5 in the following argument. If we choose to fix the expected
type-1 error rate, on the other hand, we instead consider the Bayes factor in
eq. 4.4 in the following argument.

By an application of the Neyman-Pearson lemma for Bayes factors, the most
powerful test at a fixed size should be a threshold on $B$,
$\mathcal{R}=\left\\{T:\,B(T)\geq B_{0}\right\\}$. As the Bayes factor is a
monotonic function of $T$, this is equivalent to a threshold on $T$,
$\mathcal{R}=\left\\{T:\,T\geq T_{0}\right\\}$. As $T_{0}$ can be found
independently from the prior
$p\mathopen{}\left(\boldsymbol{\theta}_{1}\,\middle|\,H_{1}\right)\mathclose{}$
by eq. 3.2 or 3.4, it must be the most powerful test for any choice of prior
$p\mathopen{}\left(\boldsymbol{\theta}_{1}\,\middle|\,H_{1}\right)\mathclose{}$,
including point masses at any particular values of the unknown parameters.
Thus, it is the UMPT.

We thus find connections between the Bayes factor and the UMPT. By
generalising the Karlin-Rubin theorem, we find that a UMPT exists whenever the
Bayes factor is a monotonic function of a sufficient statistic for any choice
of prior for the unknown parameters in the alternative model. The Bayes factor
corresponding the observed $T$ must, however, depend on the choices of prior.

##  5 Reflections

The Neyman-Pearson lemma leads to optimal test statistics for null hypothesis
significance tests for simple hypotheses. Interpreting the Bayes factor as a
likelihood ratio for two simple models leads to a Bayesian interpretation of
the Neyman-Pearson lemma that goes beyond simple models. The Bayes factor
maximises the expected power for a test of a fixed expected size.

On the Bayesian side, this could provide further justification for using Bayes
factors for objective Bayesians or more generally those who are concerned
about the frequentist properties of Bayes factors. If we place a threshold on
the Bayes factor, for whatever type-1 error rate it to which that threshold
corresponds, the Bayes factor was the statistic that maximised the expected
power. On the frequentist side, even if you want to carry on computing
p-values, there is justification for doing so using the Bayes factor as a test
statistic, especially in the case of simple null hypotheses but composite
alternatives. In the case of simple null hypotheses, using the Bayes factor
results in the best _expected_ power for a fixed completely frequentist type-1
error rate. The only concession required is that to construct the test we must
choose a weight function that marks where we want power and talk about
expected power. The test itself would, however, remain strictly frequentist.

The Karlin-Rubin theorem extends the Neyman-Pearson lemma to particular
composite models. We found that the conditions of the Karlin-Rubin theorem may
be recast as the requirement that the Bayes factor is a monotonic function of
a sufficient statistic for any choices of prior for unknown parameters. This
lead to a slightly novel proof of a generalised Karlin-Rubin theorem and a
connection between the properties of Bayes factors and the existence of
uniformly most powerful tests. The Bayesian interpreted Karlin-Rubin theorem
provides conditions under which a test of fixed size always maximises the
expected power, regardless which prior was chosen for the unknown parameters
in the alternative hypothesis in the computation of the expected power.

These results could help synthesise frequentist and Bayesian procedures, as it
shows that the Bayes factors could lie at the heart of each one, and
proponents of either should be interested, in principle, in computing the
Bayes factor. The outstanding difference would be that the Bayesian would
consider the magnitude of the observed Bayes factor, in accordance with the
likelihood principle (Berger and Wolpert, 1984), whereas the frequentist would
consider the probability of obtaining a Bayes factor more extreme than that
observed. In practice, computing the Bayes factor and finding its distribution
could be challenging, as popular asymptotic approaches such as Wilks’ theorem
(Wilks, 1938) needn’t apply (though see Severeni (2010)).

##  Appendix A Karlin-Rubin conditions for Bayes factors

Let us check the implications of the MLR conditions in the Karlin-Rubin
theorem on the Bayes factor. For the hypotheses under consideration in the
Karlin-Rubin theorem in eq. 4.1, the Bayes factor could be written

$B(T)=\frac{\int_{\theta>\theta_{C}}p\mathopen{}\left(T\,\middle|\,\theta\right)\mathclose{}\,p\mathopen{}\left(\theta\,\middle|\,H_{1}\right)\mathclose{}\,\text{d}\theta}{\int_{\theta\leq\theta_{C}}p\mathopen{}\left(T\,\middle|\,\theta\right)\mathclose{}\,p\mathopen{}\left(\theta\,\middle|\,H_{0}\right)\mathclose{}\,\text{d}\theta}$
(A.1)

for some suitably normalised choices of prior densities
$p\mathopen{}\left(\theta\,\middle|\,H_{1}\right)\mathclose{}$ and
$p\mathopen{}\left(\theta\,\middle|\,H_{0}\right)\mathclose{}$. Starting from
eq. 4.2, for $T^{\prime}>T$ and $\theta>\theta^{\prime}$, we have

$\displaystyle\frac{p(T^{\prime}\,|\,\theta)}{p(T^{\prime}\,|\,\theta^{\prime})}$
$\displaystyle\geq\frac{p(T\,|\,\theta)}{p(T\,|\,\theta^{\prime})}$ (A.2)
$\displaystyle\frac{p(T^{\prime}\,|\,\theta)}{p(T^{\prime}\,|\,\theta^{\prime})}\,\frac{p(\theta\,|\,H_{1})}{p(\theta^{\prime}\,|\,H_{0})}$
$\displaystyle\geq\frac{p(T\,|\,\theta)}{p(T\,|\,\theta^{\prime})}\,\frac{p(\theta\,|\,H_{1})}{p(\theta^{\prime}\,|\,H_{0})}$
(A.3)
$\displaystyle\left[p\mathopen{}\left(T^{\prime}\,\middle|\,\theta\right)\mathclose{}\,p\mathopen{}\left(\theta\,\middle|\,H_{1}\right)\mathclose{}\right]\left[p\mathopen{}\left(T\,\middle|\,\theta^{\prime}\right)\mathclose{}\,p\mathopen{}\left(\theta^{\prime}\,\middle|\,H_{0}\right)\mathclose{}\right]$
$\displaystyle\geq\left[p\mathopen{}\left(T\,\middle|\,\theta\right)\mathclose{}\,p\mathopen{}\left(\theta\,\middle|\,H_{1}\right)\mathclose{}\right]\left[p\mathopen{}\left(T^{\prime}\,\middle|\,\theta^{\prime}\right)\mathclose{}\,p\mathopen{}\left(\theta^{\prime}\,\middle|\,H_{0}\right)\mathclose{}\right]$
(A.4)

where we multiplied each side by the ratio of prior densities that appear in
the Bayes factor and rearranged terms. Integrating each side with respect to
$\theta$ and $\theta^{\prime}$ only over the regions guaranteeing
$\theta>\theta^{\prime}$, we find

$\begin{split}\int_{\theta>\theta_{C}}p\mathopen{}\left(T^{\prime}\,\middle|\,\theta\right)\mathclose{}\,p\mathopen{}\left(\theta\,\middle|\,H_{1}\right)\mathclose{}\,\text{d}\theta\,&\int_{\theta\leq\theta_{C}}p\mathopen{}\left(T\,\middle|\,\theta\right)\mathclose{}\,p\mathopen{}\left(\theta\,\middle|\,H_{0}\right)\mathclose{}\,\text{d}\theta\geq\\\
&\int_{\theta>\theta_{C}}p\mathopen{}\left(T\,\middle|\,\theta\right)\mathclose{}\,p\mathopen{}\left(\theta\,\middle|\,H_{1}\right)\mathclose{}\,\text{d}\theta\,\int_{\theta\leq\theta_{C}}p\mathopen{}\left(T^{\prime}\,\middle|\,\theta\right)\mathclose{}\,p\mathopen{}\left(\theta\,\middle|\,H_{0}\right)\mathclose{}\,\text{d}\theta.\end{split}$
(A.5)

Finally, we rearrange terms to find

$\begin{split}\frac{\int_{\theta>\theta_{C}}p\mathopen{}\left(T^{\prime}\,\middle|\,\theta\right)\mathclose{}\,p\mathopen{}\left(\theta\,\middle|\,H_{1}\right)\mathclose{}\,\text{d}\theta}{\int_{\theta\leq\theta_{C}}p\mathopen{}\left(T^{\prime}\,\middle|\,\theta\right)\mathclose{}\,p\mathopen{}\left(\theta\,\middle|\,H_{0}\right)\mathclose{}\,\text{d}\theta}\geq\frac{\int_{\theta>\theta_{C}}p\mathopen{}\left(T\,\middle|\,\theta\right)\mathclose{}\,p\mathopen{}\left(\theta\,\middle|\,H_{1}\right)\mathclose{}\,\text{d}\theta}{\int_{\theta\leq\theta_{C}}p\mathopen{}\left(T\,\middle|\,\theta\right)\mathclose{}\,p\mathopen{}\left(\theta\,\middle|\,H_{0}\right)\mathclose{}\,\text{d}\theta}\end{split}$
(A.6)

such that $B(T^{\prime})\geq B(T)$ for $T^{\prime}\geq T$. We did not make use
of any properties of any particular choice of prior densities. In other words,
the ordinary MLR conditions of the Karlin-Rubin theorem mean that the Bayes
factor is a monotonic function of $T$ for any choices of prior densities
$p\mathopen{}\left(\theta\,\middle|\,H_{1}\right)\mathclose{}$ and
$p\mathopen{}\left(\theta\,\middle|\,H_{0}\right)\mathclose{}$.

## References

  * Bayarri et al. (2016) Bayarri, M., Benjamin, D. J., Berger, J. O., and Sellke, T. M. (2016).  “Rejection odds and rejection ratios: A proposal for statistical practice in testing hypotheses.”  Journal of Mathematical Psychology, 72: 90 – 103.
  * Benjamin et al. (2018) Benjamin, D. J., Berger, J. O., Johannesson, M., Nosek, B. A., Wagenmakers, E.-J., Berk, R., Bollen, K. A., Brembs, B., Brown, L., Camerer, C., et al. (2018).  “Redefine statistical significance.”  Nature Human Behaviour, 2(1): 6–10.
  * Berger (2003) Berger, J. O. (2003).  “Could Fisher, Jeffreys and Neyman Have Agreed on Testing?”  Statist. Sci., 18(1): 1–32.
  * Berger et al. (1997) Berger, J. O., Boukai, B., and Wang, Y. (1997).  “Unified frequentist and Bayesian testing of a precise hypothesis.”  Statistical Science, 12(3): 133 – 160.
  * Berger and Wolpert (1984) Berger, J. O. and Wolpert, R. L. (1984).  The likelihood principle., volume 6.  Hayward, CA: IMS, Institute of Mathematical Statistics.
  * Casella and Berger (2002) Casella, G. and Berger, R. L. (2002).  Statistical inference, volume 2.  Duxbury Pacific Grove, CA.
  * Consonni et al. (2018) Consonni, G., Fouskakis, D., Liseo, B., and Ntzoufras, I. (2018).  “Prior Distributions for Objective Bayesian Analysis.”  Bayesian Anal., 13(2): 627–679.
  * Edwards et al. (1963) Edwards, W., Lindman, H., and Savage, L. J. (1963).  “Bayesian Statistical Inference for Psychological Research.”  Psychological Review, 70(3): 193–242.
  * Good (1957) Good, I. J. (1957).  “Saddle-point Methods for the Multinomial Distribution.”  The Annals of Mathematical Statistics, 28(4): 861 – 881.
  * Good (1961) — (1961).  “Weight of evidence, causality and false-alarm probabilities.”  In Information Theory: Fourth London Symposium, Butterworth: London, 125–136.
  * Good (1992) — (1992).  “The Bayes/Non-Bayes Compromise: A Brief Review.”  Journal of the American Statistical Association, 87(419): 597–606.
  * Good and Crook (1974) Good, I. J. and Crook, J. F. (1974).  “The Bayes/Non-Bayes Compromise and the Multinomial Distribution.”  Journal of the American Statistical Association, 69(347): 711–720.
  * Ioannidis (2005) Ioannidis, J. P. A. (2005).  “Why Most Published Research Findings Are False.”  PLOS Medicine, 2(8).
  * Jeffreys (1939) Jeffreys, H. (1939).  The Theory of Probability.  Oxford Classic Texts in the Physical Sciences. Oxford University Press.
  * Kass and Raftery (1995) Kass, R. E. and Raftery, A. E. (1995).  “Bayes Factors.”  Journal of the American Statistical Association, 90(430): 773–795.
  * Kass and Wasserman (1996) Kass, R. E. and Wasserman, L. (1996).  “The Selection of Prior Distributions by Formal Rules.”  Journal of the American Statistical Association, 91(435): 1343–1370.
  * Lakens et al. (2018) Lakens, D., Adolfi, F. G., Albers, C. J., Anvari, F., Apps, M. A., Argamon, S. E., Baguley, T., Becker, R. B., Benning, S. D., Bradford, D. E., et al. (2018).  “Justify your alpha.”  Nature Human Behaviour, 2(3): 168–171.
  * Lehmann (1958) Lehmann, E. L. (1958).  “Significance Level and Power.”  The Annals of Mathematical Statistics, 29: 1167–1176.
  * Lindley (1953) Lindley, D. V. (1953).  “Statistical Inference.”  Journal of the Royal Statistical Society Series B (Methodological), 15: 30–76.
  * McShane et al. (2019) McShane, B. B., Gal, D., Gelman, A., Robert, C., and Tackett, J. L. (2019).  “Abandon statistical significance.”  The American Statistician, 73(sup1): 235–245.
  * Mudge et al. (2012) Mudge, J. F., Baker, L. F., Edge, C. B., and Houlahan, J. E. (2012).  “Setting an Optimal $\alpha$ That Minimizes Errors in Null Hypothesis Significance Tests.”  PLOS ONE, 7(2): 1–7.
  * Neyman (1977) Neyman, J. (1977).  “Frequentist Probability and Frequentist Statistics.”  Synthese, 36(1): 97–131.
  * Neyman et al. (1933) Neyman, J., Pearson, E. S., and Pearson, K. (1933).  “IX. On the problem of the most efficient tests of statistical hypotheses.”  Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 231(694-706): 289–337.
  * Savage (1961) Savage, L. J. (1961).  “The foundations of statistics reconsidered.”  In Proc. 4th Berkeley Sympos. Math. Statist. and Prob., Vol. I, 575–586. Univ. California Press, Berkeley, Calif.
  * Severeni (2010) Severeni, T. A. (2010).  “Likelihood ratio statistics based on an integrated likelihood.”  Biometrika, 97(2): 481–496.
  * Wilks (1938) Wilks, S. S. (1938).  “The Large-Sample Distribution of the Likelihood Ratio for Testing Composite Hypotheses.”  Ann. Math. Statist., 9(1): 60–62.
  * Zhang (2017) Zhang, J. (2017).  “Bayesian (mean) most powerful tests.”  Australian & New Zealand Journal of Statistics, 59(1): 43–56.


# Rewrite to Reinforce: Rewriting the Binary to Apply Countermeasures against
Fault Injection

Pantea Kiaei  Worcester Polytechnic Institute  Cees-Bart Breunesse  Riscure
Mohsen Ahmadi  Arizona State University  Patrick Schaumont  Worcester
Polytechnic Institute  Jasper van Woudenberg  Riscure

###### Abstract

Fault injection attacks can cause errors in software for malicious purposes.
Oftentimes, vulnerable points of a program are detected after its development.
It is therefore critical for the user of the program to be able to apply last-
minute security assurance to the executable file without having access to the
source code. In this work, we explore two methodologies based on binary
rewriting that aid in injecting countermeasures in the binary file. The first
approach injects countermeasures by reassembling the disassembly whereas the
second approach leverages a full translation to a high-level IR and lowering
that back to the target architecture.

###### Index Terms:

Fault injection, binary protection, targeted countermeasures, automated
countermeasure, binary rewriting

##  I Introduction

Nowadays, the Fault Injection (FI) hardware attacks are becoming more
prevalent. Successful fault attacks lead to information leakage [1], [2] or
privilege escalation. While fault injection is targeted at the hardware (e.g.,
clock glitching), consequences of the resulting faults may affect the software
running on a processor. For example, ARM’s secure boot can be affected by
voltage glitching to enable an attacker to load controlled values in the
program counter (PC) [3]. Furthermore, Vasselle et al. [4] show how laser
injected faults can bypass the secure bootloader on an android smartphone.

To defend against these attacks, an extensive amount of countermeasures have
been proposed that can be categorized in three groups [5], namely those that
can be applied to the software source code, those that are implemented within
the compiler tool-chain, and those that are directly applied to the execution
binary. The first two categories require access to the source code of the
program which may not be practical in some scenarios. For instance, binary-
level protection is useful for legacy binary code, or for third-party library
code, or even for binary code for which the source code has been lost. In this
paper, we target the problem of applying FI countermeasures when we do not
have access to the source code of the program. Knowing that applying
countermeasures directly to the binary file is not easy, we demonstrate how
static binary rewriting approaches help with instrumenting the program with
our countermeasures. We apply and evaluate two static binary rewriting
schemes; One reassembleable disassembly and the other complete translation.
Using the reassembleable disassembly method, we demonstrate how we can apply
simple fixes to the binary file with low overhead. Using the full-translation
to LLVM-IR approach, we show how more complex countermeasures can be
implemented exploiting the power of an intermediate representation (IR).

The rest of the paper is organized as the following: In Section II, we discuss
the related work. In Section III, we give a brief background on binary
rewriting. In Section IV, we introduce our countermeasure insertion
methodologies. In Section V, we show the results of simple FI countermeasures
implemented using our proposed approaches. Finally, in Section VI, we conclude
the paper.

##  II Related Work

Figure 1: Coverage percentage achieved over for the cover sizes of different
sizes

While the bulk of fault countermeasures is based in detecting faults in
redundant design, researchers have made many different proposals regarding the
format and abstraction level of these redundancies. Some of the related work
start from the source code and add the countermeasure at that high level of
abstraction. For instance, Lalande et al. [6] proposed a counter-based
approach in which a counter is incremented and checked after a set number of
instructions to detect jump attacks. In other works, the countermeasures are
added at compile time and require access to the source code. Barry et al.
modified the LLVM back-end for insertion of countermeasures against
instruction-skip fault attacks. For this purpose, they duplicated instructions
based on whether the operation is idempotent [7]. Our focus is on scenarios
where the source code of the program is unavailable and we need to protect the
executable file against fault attacks. Given-Wilson et al. [8] propose a
methodology to detect vulnerabilities of program binaries to fault injection.
In their methodology, they annotate the source code with safety properties and
detect vulnerabilities when these properties are shown to not be held using
model-checking. Bréjon et al. [9] propose a framework consisting of symbolic
execution, static analysis, and model-checking to find vulnerabilities in the
binary file. Both of these works focus on finding vulnerabilities but once the
vulnerabilities are found, the source code should be accessible to add
corresponding countermeasures. De Keulenaer et al. [10] use the link-time
optimizer tool Diablo [11] and look for patterns of instructions in the
assembly-level IR that are known to be vulnerable to fault injection and
replace them with hardened code. They show the approach of using the assembly-
level IR results in a more compact hardened code, compared to the compiler-
level IR, which is important for small embedded systems. In another work,
O’sullivan et al. [12] propose a lifting and rewriting methodology based on
the SecondWrite tool [13] for hardening a binary file against low-level
software attacks such as buffer overflow attacks. Fault injection attacks are
not considered in their work.

In this project, we propose two different approaches to find the
vulnerabilities in the binary code against fault injection attacks and add
corresponding countermeasures. As the first contribution of this paper, we
propose a simulation-driven countermeasure insertion. In this method, only the
vulnerable parts of the binary file are patched and hence the overhead of the
protected code is decreased compared to a full application of the
countermeasure. As a second contribution, this work for the first time shows
how lifting the binary to an IR can help in adding countermeasures against
fault attacks. We use two different IR levels to this end and compare their
resulting overhead.

##  III Binary Rewritering

In this section, we will go through the publicly available binary rewriting
solutions and compare their approach with regard to structural recovery, data
type extraction, and limitations on supported architectures.

###  III-A Definition

Binary rewriting is denoted as the process of modifying a compiled program in
such a way that it remains executable and functional without having access to
the source-code. There are two types of binary modifiers, static and dynamic.
In the static approach, results of the modification will be stored on a
persistent memory like disk for future execution. However, dynamic rewriting
is applied during the program execution. In this paper we focus on static
binary rewriting technique and compare the tools following this scheme.

Based on Figure 1, from a high-level view, in the first step ( 1), a binary
rewriter receives a file in a binary stream format as input and passes it to
the disassembler for decoding the instructions, and retrieving global
variables and sections. Decoded instructions help step 2 in building the
control and data flow, recovering data types, and function boundaries to
semantically enriching the context with metadata lost during the compilation.
Transformation step ( 3) modifies the target binary in a way that mutated
output is a working executable.

###  III-B Static Binary Rewriting

There are three known rewriting schemes. The oldest one is based on detouring
at assembly level. Detouring works by hooking out the underlying instruction.
There are two flavors of the detouring technique, patch-based instrumentation
and replica-based instrumentation. Patch-based instrumentation replaces the
instruction with an unconditional branch to a new section containing
instrumentation, replaced instruction, and a control flow transfer back to the
patch point. Detouring is a direct rewriting and is ISA dependant which makes
the approach inconvenient. This approach introduces a high performance
degradation given the two control transfers at patch points.

Replica-based instrumentation method inserts jump instructions to a replicated
code section containing both a copy of the original code and the
instrumentation. All memory references in this section are modified to
maintain fewer control flow transfers between original and replicated section.
While the performance of this approach is better compared to the patch-based
instrumentation, the size of the resulting binary is noticeably increased.

Reassembleable disassembly works by recovering relocatable assembly code, the
instrumentation of which could be inlined and reassembled back to a working
binary. This approach first introduced by UROBOROS [14] and then expanded by
improving on top of the idea in Ramblr [15]. This approach enhances the
performance since inlined assembly avoids inserting control flow changing
instructions at instrumentation points. As a result, performance penalty
caused by jump instructions are alleviated in this technique.

Full-translation approach works upon translating a low-level machine code to a
high-level intermediate representation (IR) using a compiler-based front-end
for architecture independent binary rewriting. This process is called lifting
the binary and assembling the IR back to a working executable is denoted as
lowering. The advantage of lifting the binary to a high-level IR are two fold.
First, relying on IR makes the rewriting framework ISA-agnostic; Second,
working on a high-level IR provides the ability to apply program analysis
techniques like Value Set Analysis (VSA) [16] and optimization passes like
Simple Expression Tracker (SET) and Offset Shifted Register Analysis (OSRA)
[17]. On the other hand, complete translation suffers from changing the
structural integrity such as cache locality and Control Flow Graph (CFG).

While each approach has its own drawbacks and benefits, we focused our
evaluation on two recent research: Datalog Disassembly (Ddisasm) [18] for
reassembling the disassembly and Rev.ng [17] as the candidate for full-
translation.

###  III-C Comparison of Binary Rewriters

In this section, we briefly describe the reasons behind choosing the above-
mentioned two binary rewriters as our candidates. During the linking phase,
linker replaces the symbolic labels with concrete memory addresses which
results in losing the relocation information. Hence, to perform rewriting
tasks, we need to recover the symbolic references from absolute addresses. A
process which is called symbolization. Symbolization aims to distinguish
whether an intermediate value belongs to a symbol or treat the value as a
constant integer.

Comparing reassembling methods, Ramblr provided counter-examples in real-world
binaries for which the UROBOROS symbol categorization fails. UROBOROS scans
the data section linearly and considers any machine word-sized buffer whose
integer representation falls in a memory region as a memory reference. This
assumption with the compiler optimization introduces False-positive and False-
negatives.

Ramblr improved the content classification by applying strong heuristics like
localized VSA and Intra-function data dependence analysis. To improve the
binary rewriting results, Ramblr depends heavily on symbolic execution for
accurate CFG recovery which slows down the rewriting process and brings up
scalability issues.

Apart from Ramblr’s heuristics, Ddisasm incorporated register value analysis
as an alternative over traditional VSA. In addition, they introduced Data
Access Pattern (DAP) analysis which is a def-use analysis combined with the
results of register value analysis for a refined register value inference at
any given data access point.

Rev.ng relies on full binary translation by lifting the binary to TCG (the IR
used in QEMU [19]) and para-lifting TCG to LLVM-IR to benefit from more
advanced transformation and analysis passes for CFG and function boundary
recovery. While frameworks like angr [20] use lifting to apply more advanced
binary analysis on top of the intermediate-level representation, they do not
lower the resulting transformation back to the binary. Moreover, Rev.ng
heavily relies on code pointers for identifying function entry points and
leverages VSA for a more precise value boundary tracking.

As the rewriter tools to harden the binary code against fault injection, in
this work, we chose Ddisasm and Rev.ng to show the difference between two
different rewriting schemes for this purpose.

##  IV Countermeasure Insertion Methodology

For complex architectures, like x86-64, it is not straight forward to group
the bits in the binary file to form full instructions. Neither is it easy to
group the instructions to form basic blocks at this level of abstraction.
Therefore, manipulating the binary file directly is not trivial. We propose a
procedure in which we use an open source disassembler and binary manipulation
tools as well as binary lifters to make the binary hardening process more
manageable.

###  IV-A Rewriting the Binary

Using the disassemblers and working on the assembly code, compared to the
binary file, can help in finding patterns of instructions and applying fixes
locally. However, at the assembly code level, the register allocation and
memory usage are fixed. Therefore, applying fixes at this level requires extra
caution not to overwrite the allocated registers in use. A favorable property
of this level of hierarchy is that we know which part of the assembly code
corresponds to which part of the machine code exactly. We take advantage of
this property in our proposed methodology and build an iterative process that,
using simulation of fault effects, can locally apply countermeasures only to
the parts that they are required.

While simple and small fixes can be applied at the assembly level, more
complex fixes are not easily applicable. In this case, a higher level of
abstraction that enables modification of the code and different types of
analysis is useful. Since LLVM-IR is in Single Static Assignment (SSA) [21]
format and supports different levels of hierarchy (namely module, function,
basic-block, and instruction), we choose it as our high-level IR. Support of
different levels of hierarchy in the IR makes it easier to perform static
analyses on the program. Additionally, being a part of the LLVM tool-chain,
has the advantage of being open-source, having a big number of active
contributors, and a well-maintained documentation. Despite the aforementioned
advantages, however, lifting the binary to such a high level of abstraction
will eliminate the mapping between the abstraction levels. This results from
the fact that the high level of abstraction lacks the low-level target-
dependent information. Consequently, applying targeted and local fixes to the
binary files at this high level of abstraction is not readily available.

In the following subsections, we discuss the mentioned approaches to
countermeasure injection.

###  IV-B Faulter+Patcher Approach

Figure 2: Flowchart of the Faulter+Patcher approach

Our first approach injects countermeasures at the abstraction level of
assembly code and is thus able to patch the binary file in a targeted manner.
Fig. 2 shows the overall scheme. In this approach, we have a fault simulation-
driven, iterative method to mitigate fault injection vulnerabilities in the
binary file. The system consists of two main components: a faulter and a
patcher. The faulter is simulating faults under a certain fault model in a
target binary and produces a list of vulnerabilities, meaning faults where
unwanted behavior in the target binary is triggered. The patcher uses the list
produced by the faulter to patch the binary. The patcher will patch each fault
vulnerability as localized as possible, without affecting its surrounding
code. The patched binary is then again run through the faulter and patcher. We
repeat this process until no more faults are present or can be fixed. In the
following, the faulter and the patcher are discussed in detail.

####  IV-B1 Faulter

For our purpose, fault injection vulnerabilities are vulnerabilities where an
attacker, i.e. an unauthorized user, is able to trigger a behavior in a target
binary that should be reserved only for authorized users. For example,
consider a pincode checker that receives an input pin and checks if the
inserted value is correct. For a correct pin, the program will proceed to run
some sensitive operations. An attacker does not know the correct pincode, but
may be able to skip an instruction in the target binary such that the program
will conclude the inserted pin is correct and therefore run the sensitive
operations. These faults are labeled “successful faults”. Faults that do not
trigger the unwanted behavior or cause the program to crash are ignored.

We first choose a fault model that we want to protect our binary file against.
Regardless of the fault model, and the number of faults injected per run, the
faulter takes a target binary and two inputs; a “good” input and a “bad”
input. For instance, in the pincheck example, the “good” input is the correct
pincode and the “bad” input is any value other than the correct pincode.
First, the “good” and the “bad” inputs are executed to see the difference of
execution traces between them. When running the target binary with the “bad”
input, we effectively can record a trace of all the instructions executed. For
each offset in that trace, taking the “single bit flip model” as an example,
we run the target binary normally up to that offset in the trace, flip a bit
in the instruction at the trace offset, and then resume execution. The target
binary either crashes, executes as an incorrect input, or behaves differently
(as a correct input). If it behaves as a correct input, the trace offset and
the fault that caused it, in this case a bit offset into an instruction at the
trace offset, is recorded.

We implemented this simple faulter in Python using the Qiling binary emulator
package. We fork each fault simulation to speed up the process. Our faulter
supports x86-64 Linux binaries only, but including support for other
architectures supported by Unicorn should be straightforward.

####  IV-B2 Patcher

The list of “successfult faults” coming out of the faulter is addressed
locally in the patcher. The patcher replaces the vulnerable patterns of
instructions with known hardened patterns. For example, consider a run of the
faulter under the “instruction skip” fault model that identified that at
timestamp 40, the skipping of a mov instruction is a successful fault. A local
countermeasure is to perform the mov twice, or add a compare instruction to
verify the mov has been executed prior. Note that these countermeasures cause
duplicate reads, as redundancy is key to mitigate fault injection attacks.

We implemented a proof of concept patcher based on GrammaTech’s Ddisasm tool
and their Python binary manipulation libraries. The Ddisasm tool performs
pointer analysis on an executable and produces an IR in the form of GrammaTech
Intermediate Representation for Binaries (GTIRB) [22] that can then be
manipulated and recompiled into an executable by the Python GTIRB libraries.

####  IV-B3 Rinse and repeat

After running the faulter and the patcher once, we end up with a patched
binary. Running the faulter on the patched binary may reveal that, since we
added code and changed distances between instructions, we added new
vulnerabilities. These new vulnerabilities then can be addressed by running
the patcher iteratively until a fixed point is reached.

###  IV-C Hybrid Compiler-Binary Approach

In our second approach, we inject countermeasures at the abstraction level of
compiler IR. To be able to implement more complex countermeasures, working at
the level of assembly code is cumbersome if not impractical. For example,
consider a countermeasure where extra registers are needed to hold some
intermediate values. If the assembly code had been generated with a high level
of optimization and no register is available in the unprotected program, extra
steps should be taken to spill some data to the memory to make a few registers
available and load them back to the same registers after the countermeasure.
This requires knowledge of the state of the memory at different locations.
However, there is no guarantee that these steps are possible therefore
implementing some countermeasures on certain programs might not be feasible.

To overcome this problem, we propose a process as shown in the upper half of
Fig. 3. This process consists of three steps; First, we transform the program
from binary to a compiler IR. Second, we implement the countermeasure on the
IR. Last, we transform the protected IR back to the executable binary format,
hence, achieve the goal of protecting the binary file. These steps are
elaborated in the rest if this section.

Figure 3: High-level overview of the Faulter+Patcher (lower half) and the
Hybrid (upper half) approaches

####  IV-C1 Transforming to an intermediate representation

The goal of this step is to have a representation of the binary file which,
while preserving the functionality, is easier to modify and supports a format
in which different types of analysis can be performed. As discussed earlier,
we choose LLVM-IR.

There are several open-source tools that are able to lift the binary file of
different architectures to the architecture-independent form of LLVM-IR. In
this work, we use Rev.ng. As mentioned in Section III, Rev.ng is a binary
analysis framework based on QEMU and LLVM. As part of this framework, it is
possible to extract the LLVM-IR of a program from its binary. The binary file
can be for any of the x86, x86-64, ARM, MIPS, s390x, or AArch64 (WIP)
architectures. In this project, without loss of generality, our focus is on
the x86-64 architecture.

####  IV-C2 Implementing the countermeasure

After the lifting step is performed, we have the LLVM-IR representation of the
algorithm. Therefore the countermeasure can be implemented in the form of a
combination of optimization and/or back-end passes depending on the desired
protection. If the protection algorithm does not have any dependencies
specific to the target architecture, the entire countermeasure can be in the
form of an optimization pass. Otherwise, back-end passes would be required.

####  IV-C3 Generating the protected executable

Finally, the protected IR needs to be compiled to an executable. In LLVM, the
llc tool is responsible for translating the LLVM-IR to an architecture-
specific executable file. Specific steps might need to be added in the form of
back-end passes to make sure the implemented countermeasures are retained
unchanged through this process. Once the hardened binary file is generated, we
use the same faulter system to detect remaining vulnerabilities.

###  IV-D Choosing the Right Method

The targeted insertion of countermeasures in the Faulter+Patcher scheme makes
the overhead of the applied assurance smaller than a holistic approach.
Furthermore, the mere act of lifting the binary to LLVM-IR and translating it
back to binary in the Hybrid approach adds extra overhead to the program. This
stems from the internal functions of the binary rewriting tools, which in our
case is Rev.ng. On the other hand, applying countermeasures in the Hybrid
approach is easily automated and is guaranteed to be feasible. The hierarchy
levels supported by LLVM-IR as well as its SSA format eases many static
analyses such as finding idempotent pieces, finding and replacing all the uses
of a variable, and many more.

The aforementioned trade-off between these methods, makes each method suitable
for a different use case scenario. In size-constrained applications, such as
programs for small embedded systems, the Faulter+Patcher method is more
favorable due to its smaller footprint. In scenarios where the code size is
not of critical concern, the Hybrid approach provides a simpler and guaranteed
assurance for inserting complex countermeasures.

##  V Experimental Results

In this section, we show how our proposed approaches can apply countermeasures
against a chosen fault model. We first show the local protections that we add
by our Faulter+Patcher approach. We then demonstrate a holistic protection
that can be used in our Hybrid approach. Finally, we show the results of the
inserted countermeasures in our case studies.

###  V-A Local Protections

TABLE I: Local protection pattern for mov operations Original | Protected
---|---
| mov rax, [rbx+4]
---
happyflow: …
| mov rax, [rbx+4]
---
cmp rax, [rbx+4]
je happyflow
call faulthandler
happyflow: …
TABLE II: Local protection pattern for cmp operations

Original | Protected
---|---
| cmp rbx, [rcx+4]
---
fallthrough: …
| lea rsp, [rsp-128]
---
cmp rbx, [rcx+4]
push rbx
pushfq
cmp rbx, [rcx+4]
pushfq
pop rbx
cmp rbx, [rsp]
je restore
call faulthandler
resotre:
popfq
pop rbx
lea rsp, [rsp+128]
fallthrough: …

TABLE III: Local protection for conditional jump operation

Original | Protected
---|---
| j<cond>jumptarget
---
fallthrough: …
jumptarget: …
| j<cond>newjumptarget
---
lea rsp, [rsp-128]
push rcx
pushfq
set cl
cmp cl, 0
je newfallthroughjmp
call faulthandler
newfallthroughjmp:
popfq
pop rcx
j<cond>fallthrough
call faulthandler
newjumptarget:
lea rsp, [rsp-128]
push rcx
pushfq
set cl
cmp cl, 1
je newjumptargetjmp
call faulthandler
newjumptargetjmp:
popfq
pop rcx
j<cond>jumptarget
call faulthandler
fallthrough: …
jumptarget: …

In the Faulter+Patcher approach, we are able to insert protected code patterns
locally. The following is the description of these redundant computation-based
protections.

####  V-A1 Protecting mov Instruction

To protect the mov operation against fault attacks, after executing the mov
operation, the result of the two memory locations are compared and in case of
an inconsistency, a faulthandler is called (Table I).

####  V-A2 Protecting the cmp Instruction

We can protect a cmp instruction against fault attacks by executing the
comparison twice and comparing their resulting flags (Table II). To this end,
we use the pushfq instruction in x86-64 ISA which requires a valid stack
pointer (rsp). Due to Intel’s red zone, we have to subtract 128 bytes from rsp
to jump out of the red zone.

####  V-A3 Protecting the j<cond> operation

By hardening the conditional jump operations, we detect glitches that change
the jump condition. In the protected code shown in Table III, we use the flags
register and match this to the expected flag in the jump-target and the fall-
through of a branch.

###  V-B Holistic Protection

[] cmp rs1, rs2 bne target2 … target1: … target2: …

Figure 4: Assembly code and CFG of a simple branch instruction

In this section, we describe a conditional branch hardening method that we
later use in our case studies for the Hybrid countermeasure implementation
approach.

Imagine a simple program that receives a pin code and only if the pin code is
correct, resumes the program to execute some operations. In the assembly code
(equally the executable file) of this program, there will be a comparison
instruction to compare the inserted pin code and its expected value, as well
as a conditional branch that, based on the result of the comparison, jumps to
a successor basic block. Figure 4 shows the assembly code and the control flow
graph (CFG) of this branch operation.

In the case of Control Flow Integrity (CFI), going from BB1 to either of BB2
or BB3 does not raise any issues since they both are valid paths in the CFG.
However, if an injected fault results in taking the wrong branch, it will be
an unnoticed fault. In this conditional branch hardening method, our goal is
to protect against this outcome of FI.

In this method, we assign a unique ID to each basic block ($UID_{BB}$) at
compile time. We then use an algorithm, $h(UID_{src},UID_{dst},cmp\\_res)$,
which calculates a checksum at run-time based on the fixed $UID$s assigned to
the source and destination blocks at compile-time, i.e. $UID_{src}$ and
$UID_{dst}$, and the dynamically-evaluated compare result, $cmp\\_res$. The
calculated checksum will be stored in a register and checked in the
destination basic blocks. At the destination blocks, since the expected
$cmp\\_res$ for the taken edge is known, the expected value of $h$ is known.
Therefore checking the evaluated value only requires reading the register
value and comparing it with the expected value. When the register does not
contain the expected value, we jump to a fault-response basic block.

The simplicity level of the $h$ function can be decided based on the required
security properties of the program. As an example, we chose a simple option
for $h$ and implemented the countermeasure as an optimization pass in the LLVM
tool-chain. In this example, the checksum is calculated as the XOR result of
the UID of the taken destination block and that of the source block
($UID_{dst}\oplus UID_{src}$). The pseudo-code of the calculation procedure of
this checksum in LLVM is shown in Algorithm 1 where $cmp\\_res$ is the result
of the comparison for the conditional branch, and $UID_{Tdst}$, $UID_{Fdst}$,
and $UID_{src}$ are the UIDs assigned to the true destination (the destination
taken when the comparison result is true), the false destination (the
destination taken when the comparison result is false), and the source block
respectively. The $mask$ shown on line 4 will have the value of all ones if
the comparison result is false and the value of all zeros if the comparison
result is true. The checksum will be located in one register and each of the
destination blocks will evaluate whether the value of the checksum is correct.

Furthermore, we made this evaluation duplicated; Figure 5 shows the CFG of
this implementation protecting the conditional branch shown in Figure 4. We
run the comparison instruction once (C1), and calculate the checksum based on
its result and keep it in a register (D1). We perform this calculation another
duplicated time and keep the result in a new register (D2). We then perform
the comparison again and run the branch based on the result of the second
comparison (C2). As shown by the orange boxes, the expected value of the
checksum is different for the out-going edges of the source block (N1 vs. N2).
In the destination blocks, we check both copies of the checksum stored in
registers against the expected values in a nested fashion. The green blocks
show the nested checksum validations and the blue blocks represent the fault-
response. As a simple example, the fault-response can be aborting the
execution (in the flt_respx basic blocks).

Figure 5: CFG of the example conditional branch hardening Algorithm 1 Simple
example algorithm for $h$

0: $cmp\\_res$, $UID_{Tdst}$, $UID_{Fdst}$, $UID_{src}$

0: $checksum$ Generate unique checksums for edges :

1: $const_{Tdst}\leftarrow UID_{Tdst}\oplus UID_{src}$

2: $const_{Fdst}\leftarrow UID_{Fdst}\oplus UID_{src}$ Calculate checksum of
the branch :

3: $cmp\\_ext\leftarrow zero\\_extend(cmp\\_res)$

4: $mask\leftarrow cmp\\_ext-1$

5: $checksum\leftarrow(\neg mask\land const_{Tdst})\lor(mask\land
const_{Fdst})$

In this scenario, if the attacker tries to skip one of the comparison
instructions or change it to compute the inverse output, the checksum
validation process will be able to catch the injected error. If the adversary
intends to bypass this process, they would need to inject the exact same fault
in both comparison results. In Section V-C, we show a simulated analysis of
the effectiveness of this countermeasure.

The overall overhead of this countermeasure depends on the number of
conditional branches that we want to protect and therefore is highly
application-specific. Table IV shows how many instructions are required to
replace a simple conditional branch by this method. We implement the
conditional branch hardening as an optimization pass in the LLVM compiler
tool-chain. Therefore, its translation will differ for different target
architectures based on how the instruction-lowering is done for that
architecture in the LLVM back-end.

TABLE IV: Qualitative overhead of the conditional branch hardening

Before Protection | After Protection
---|---
LLVM-IR | x86-64 | LLVM-IR | x86-64
| 1 cmp
---
1 br
| 1 cmp
---
1 jx (cond. jump)
| 1 cmp
---
2 zext
2 sub
6 xor
2 or
4 and
1 br
4 switch
| 2 cmp
---
6 mov
2 sub
6 xor
2 or
6 and
2 test
4 jx (cond. jump)
5 jmp (uncond. jump)

###  V-C Case Studies

We choose two applications for the proof of concept of our proposed methods.
The first application is a simple pin-check program that receives an input
password and checks the correctness of the inserted password. The second
application is a secure bootloader in which the hash of the content of a
memory location is calculated and compared with an expected hash value.

For each case study, we use the faulter described in Section IV-B with the two
fault models of “instruction skip” and “single bit flip” and verify that the
code has vulnerabilities to these fault models. All of these vulnerabilities
were caused by the conditional jumps (mov, cmp, and jmp instructions related
to a jump operation) in the program. We then insert the code patterns
described in Section V-A using the Faulter+Patcher approach for each
vulnerable point and reevaluate the hardened binary file iteratively until
confirmed that no more vulnerabilities exist. Furthermore, we apply the
conditional branch hardening countermeasure from Section V-B using our Hybrid
approach and verify that the vulnerabilities have been mitigated. In the case
of the “instruction skip” fault model, we were able to resolve all the
vulnerabilities using the mentioned countermeasures. In the case of the
“single bit flip” fault model we were able to reduce the number of vulnerable
points by 50% using both methodologies.

Table V shows the overhead caused by the inserted countermeasure in each
approach. The overhead caused by the Hybrid approach is 2 to 5 times bigger
than that of the iterative method. This is an expected outcome since the
Hybrid approach applies the countermeasure to the entire program whereas the
Faulter+Patcher approach only does so to the vulnerable points. Furthermore,
duplicating every instruction, which is the go-to protection scheme against
fault injection, implies at least 300% overhead in code size (since for each
instruction, it will add another copy of the instruction and a comparison
procedure between their results). Therefore, both of our methods perform
better than a simple duplication scheme.

TABLE V: Overhead of adding the protections Case Study | Overhead in code size (%)
---|---
Faulter+Patcher | Hybrid
pincheck | 17.61 | 85.88
secure bootloader | 19.67 | 48.67

##  VI Conclusion and Future Work

In this work, we proposed two approaches for hardening the binary file against
fault attacks based on binary rewriting. In the first approach, we disassemble
the binary file and insert countermeasures which enables us to insert local
countermeasure and keep the structure of the original binary file. We propose
an iterative and simulation-driven framework that only inserts countermeasures
to the vulnerable parts of the program. In the second approach, we lift the
binary file to LLVM-IR and insert countermeasures at a higher level of
abstraction. This enables us to implement more complex countermeasures and
perform static analyses on the program.

As the future work, we intend to study the mapping between the lifted LLVM-IR
of a binary code and the original binary file and enable an iterative
countermeasure insertion for the Hybrid methodology.

## References

  * [1] G. Piret and J.-J. Quisquater, “A differential fault attack technique against spn structures, with application to the aes and khazad,” in _International workshop on cryptographic hardware and embedded systems_. Springer, 2003, pp. 77–88.
  * [2] R. Leveugle, A. Calvez, P. Maistri, and P. Vanhauwaert, “Statistical fault injection: Quantified error and confidence,” in _2009 Design, Automation & Test in Europe Conference & Exhibition_. IEEE, 2009, pp. 502–506.
  * [3] N. Timmers, A. Spruyt, and M. Witteman, “Controlling pc on arm using fault injection,” in _2016 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC)_ , 2016, pp. 25–35.
  * [4] A. Vasselle, H. Thiebeauld, Q. Maouhoub, A. Morisset, and S. Ermeneux, “Laser-induced fault injection on smartphone bypassing the secure boot-extended version,” _IEEE Transactions on Computers_ , vol. 69, no. 10, pp. 1449–1459, 2020.
  * [5] N. Belleville, K. Heydemann, D. Couroussé, T. Barry, B. Robisson, A. Seriai, and H.-P. Charles, “Automatic application of software countermeasures against physical attacks,” in _Cyber-Physical Systems Security_. Springer, 2018, pp. 135–155.
  * [6] J.-F. Lalande, K. Heydemann, and P. Berthomé, “Software countermeasures for control flow integrity of smart card c codes,” in _European Symposium on Research in Computer Security_. Springer, 2014, pp. 200–218.
  * [7] T. Barry, D. Couroussé, and B. Robisson, “Compilation of a countermeasure against instruction-skip fault attacks,” in _Proceedings of the Third Workshop on Cryptography and Security in Computing Systems_ , 2016, pp. 1–6.
  * [8] T. Given-Wilson, A. Heuser, N. Jafri, and A. Legay, “An automated and scalable formal process for detecting fault injection vulnerabilities in binaries,” _Concurrency and Computation: Practice and Experience_ , vol. 31, no. 23, p. e4794, 2019.
  * [9] J.-B. Bréjon, K. Heydemann, E. Encrenaz, Q. Meunier, and S.-T. Vu, “Fault attack vulnerability assessment of binary code,” in _Proceedings of the Sixth Workshop on Cryptography and Security in Computing Systems_ , 2019, pp. 13–18.
  * [10] R. De Keulenaer, J. Maebe, K. De Bosschere, and B. De Sutter, “Link-time smart card code hardening,” _International Journal of Information Security_ , vol. 15, no. 2, pp. 111–130, 2016.
  * [11] L. Van Put, D. Chanet, B. De Bus, B. De Sutter, and K. De Bosschere, “Diablo: a reliable, retargetable and extensible link-time rewriting framework,” in _Proceedings of the Fifth IEEE International Symposium on Signal Processing and Information Technology, 2005._ IEEE, 2005, pp. 7–12.
  * [12] P. O’sullivan, K. Anand, A. Kotha, M. Smithson, R. Barua, and A. D. Keromytis, “Retrofitting security in cots software with binary rewriting,” in _IFIP International Information Security Conference_. Springer, 2011, pp. 154–172.
  * [13] K. Anand, M. Smithson, A. Kotha, K. Elwazeer, and R. Barua, “Decompilation to compiler high ir in a binary rewriter,” _University of Maryland, Tech. Rep_ , 2010.
  * [14] S. Wang, P. Wang, and D. Wu, “Uroboros: Instrumenting stripped binaries with static reassembling,” in _2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER)_ , vol. 1. IEEE, 2016, pp. 236–247.
  * [15] R. Wang, Y. Shoshitaishvili, A. Bianchi, A. Machiry, J. Grosen, P. Grosen, C. Kruegel, and G. Vigna, “Ramblr: Making reassembly great again.” in _NDSS_ , 2017.
  * [16] G. Balakrishnan and T. Reps, “Analyzing memory accesses in x86 executables,” in _International conference on compiler construction_. Springer, 2004, pp. 5–23.
  * [17] A. Di Federico, M. Payer, and G. Agosta, “rev.ng: a unified binary analysis framework to recover CFGs and function boundaries,” in _Proceedings of the 26th International Conference on Compiler Construction_ , 2017, pp. 131–141.
  * [18] A. Flores-Montoya and E. Schulte, “Datalog disassembly,” in _29th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 20)_, 2020.
  * [19] F. Bellard, “Qemu, a fast and portable dynamic translator.” in _USENIX Annual Technical Conference, FREENIX Track_ , vol. 41, 2005, p. 46.
  * [20] F. Wang and Y. Shoshitaishvili, “Angr-the next generation of binary analysis,” in _2017 IEEE Cybersecurity Development (SecDev)_. IEEE, 2017, pp. 8–9.
  * [21] B. K. Rosen, M. N. Wegman, and F. K. Zadeck, “Global value numbers and redundant computations,” in _Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages_ , 1988, pp. 12–27.
  * [22] E. Schulte, J. Dorn, A. Flores-Montoya, A. Ballman, and T. Johnson, “Gtirb: intermediate representation for binaries,” _arXiv preprint arXiv:1907.02859_ , 2019.