%!TEX root = main.tex


This section describes the algorithms for building the covert channels based on power consumption.
The algorithms do not depend on whether the channel is based on the power consumption by the CPU or
by the DRAM. We begin by describing the behavior of the Trojan process, that modulates the power consumption.
Then we discuss how a spy process can decode the message using the power measurement samples. We finish
this section with a brief discussion on strategies to synchronize the two processes.

\subsection{Trojan: modulating power consumption}
\label{sec:trojan_encoding}

Suppose we want to encode a binary message $M = (m_1, \ldots, m_n)$.
Let $A$ be the CPU or DRAM intensive task we want to use to encode the message.
Suppose we want to transmit $r$ bits per second. Let $t_s$ be the time when the transmission
is initiated. The algorithm for transmitting the message is given next.
\begin{enumerate}
    \item Set $i \gets 1$.
    \item If $m_i = 1$, run the intensive task $A$, keeping control of the current time
    $t_c$, while \label{enum:start_loop}
    \begin{equation}
        t_c - t_s < i \times 1/r \label{eq:sync}.
    \end{equation}
    \item If $m_i = 0$, wait until $t_c - t_s < i \times 1/r$
    \item Do $i \gets i + 1$.
    \item Go to step \ref{enum:start_loop} if $i \leq n$, otherwise finish.
\end{enumerate}

One of the critical steps in the modulating algorithm is given by Equation~\ref{eq:sync},
which ensures that the transmission is always synchronized with the time when the
transmission was initiated. This makes the decoding step easier.


Figure~\ref{fig:message_cmp_cpu_mem_normannot} shows the transmission of the
same 20-bit message using CPU and DRAM-based Trojans, transmitting at 100 bps.
One important observation with respect to the CPU power modulation shown in
Figure~\ref{fig:message_cmp_cpu_mem_normannot} is that the
processor needs some time to go from high to low power consumption. This behavior can
be seen in the transmission of the 3rd, 8th, and 16th bits. Therefore when implementing
the covert channel, one can consider to make the CPU-intensive task stop earlier
when going from a 1 to a 0 bit to lower the  probability of a decoding error.

\begin{figure}[!ht]
  \centering
  \includegraphics[scale=1.2]{graphs/message_cmp_cpu_mem_normannot.pdf}
  \caption{Example of two Trojans, one using CPU-based modulation (top) and the other using
  memory-based modulation (bottom), transmitting at 100 bps.}
  \label{fig:message_cmp_cpu_mem_normannot}
\end{figure}


% The variation consists
% of, when the Trojan is transmitting a message bit 1, the CPU intensive task stop earlier if the next message bit is a 0. That is, when transmitting $m_i$, if $m_i = 1$ and $m_{i + 1} = 0$,
% the Trojan performs the CPU intensive task while
% \[
%   t_c - t_s < \left(i - \frac{1}{\delta} \right) \times \frac{1}{r} \label{eq:sync_cpu},
% \]
% where $\delta$ is chosen to minimize the probability of a decoding error.
% When evaluating the quality of the covert channels in Section~\ref{sec:eval},
% we consider concrete parameters for $\delta$.


\subsection{Spy: demodulating power consumption}

Let $T = (t_1, \ldots, t_N)$, be a sequence of time points where a power measurement occurs, and
$P = (p_1, \ldots, p_N)$ be the sequence of corresponding observed values. That is, the $i$-th measurement
was made at time $t_i$ and the observed power consumption was $p_i$.
Suppose that $t_s$, the time when the message
starts being transmitted, and the number of bits to be transmitted $n$, are known. In Section~\ref{sec:sync}, we discuss briefly how $t_s$ and $n$ can be obtained by the spy process.
As in the previous section, let $r$ be the known transmission rate, that is, the
number of bits per second that the Trojan process is programmed to transmit.
Then the spy process runs the following algorithm.

\begin{enumerate}
    \item Set $i \gets 1$.
    \item Let
    \[
        S_i \gets \left\{ j \in \{1, \ldots, N\} :  \frac{(i - 1)}{r} \leq t_j - t_s <  \frac{i}{r} \right\},
    \]
    that is, $S_i$ contains the indexes of the time measurements when, ideally, the power measurements samples
    correspond to the transmission of the $i$-th message bit. \label{enum:step_loop_decode}
    \item Let
    \[
        \overline{P_i} \gets \frac{1}{|S_i|} \sum_{j \in S_i} p_j,
    \]
    that is, $\overline{P_i}$ is the average of the power measurements that correspond to the
    $i$-th message bit.
    \item If $\overline{P_i} \geq \overline{P}$, where $\overline{P}$ is some precomputed threshold, then set $\hat{m}_i \gets 1$.
    \item Else, set $\hat{m}_i \gets 0$.
    \item Do $i \gets i + 1$.
    \item If $i \leq n$, go to step~\ref{enum:step_loop_decode}. If not, return the decoded message
    $\hat{M} = (\hat{m}_1, \ldots, \hat{m}_n)$.
\end{enumerate}

It is important to note that this algorithm stays valid even if $n$ is not defined. This could be the case
when the Trojan never stops streaming the user's private data.
Figure~\ref{fig:message_cmp_cpu_mem_normannot} can help us visualize the decoding process, considering
$t_s~=~0, r~=~100, N~=~20$, and message $M = (11001110111111100000)$. The thresholds $\overline{P}$ shown in the figure depend on the type of Trojan used to encode the message.

% TODO
% Figure~\ref{fig:decoding_cc_cpu} illustrates the decoding process when using a CPU intensive task,
% with only 1 thread, where the intended message of $n = 10$ bits was $M = (1, 0, 0, 1, 0, 1, 1, 1, 0, 1)$. In this case, the transmission rate is $r = 1$ bit per second, and $t_s~=~3.4$ seconds. We can see the partitioning of the
% samples in $n$ blocks, corresponding to $S_i$, for $i = 1, \ldots, n = 10$. The brown dots
% show the values of each $\overline{P_i}$. The dotted black line corresponds to the average of all power
% consumption samples $\overline{P}$, which is used for classification. In this simple case, the decoded
% message is indeed equal to the intended message.

  % \label{fig:decoding_cc_cpu}




\subsection{Computing the threshold $\overline{P}$}

A simple method for computing the threshold $\overline{P}$ is to run simulations on the
target system to learn the distributions of the $m_i$'s' when given $P_i$'s.
If the attacker does not have access to the target system beforehand to run the simulations, but he
knows that each element of the message is independent and equally distributed over 0 and 1, he can compute
the threshold $\overline{P}$ as the average of a large number of $P_i$'s. If the attacker does not have access to
the target system,
nor does the message bits are independent and equally distributed, the Trojan and spy can use
a protocol which starts by sending an encoding of a known message so that the spy can
learn the threshold $\overline{P}$ specific for the target system.



\subsection{Synchronizing the Trojan and the spy processes}
\label{sec:sync}

It is important, for the decoding algorithm to work correctly,
that the spy knows at what time the message starts being
transmitted, denoted as $t_s$.
If the Trojan and the spy share a clock, the instant $t_s$ can be hardcoded in them.
But in a more interesting setting, where, for example, the Trojan and spy are running
in different Virtual Machines, the assumption of a shared clock is strong.

Let $M_{\text{sync}}$ be a binary message of length $n_{\text{sync}}$ hardcoded in both Trojan and spy.
The Trojan and the spy can use the following protocol for synchronization.

\begin{description}
  \item[Trojan:]\
    \begin{enumerate}
        \item To transmit a message $M$, the Trojan simply transmits $(M_{\text{sync}}, M)$
            using the encoding algorithm from Section~\ref{sec:trojan_encoding}.
    \end{enumerate}
  \item[Spy:]\
    \begin{enumerate}
      \item Read the power consumption registers continually at sample rate $T$.
      \item For each time sample $t$, try to decode the first $n_{\text{sync}}$ bits using $t_s = t$,
        and compare the result with $M_{\text{sync}}$, which is known a priori.
      \item If the number of errors is above some threshold (e.g. 15\%), discard $t$
        and try the next time sample.
      \item Else, use $t_s = t$ to decode $(M_{\text{sync}}, M)$ and obtain the message $M.$ \label{step:spy_finds_t_s}
    \end{enumerate}
\end{description}

To lower the error rates, when the spy finds a good value in step~\ref{step:spy_finds_t_s}, it
can try time samples close to $t$ to find the one which gives the lower error rate with respect
to $M_{\text{sync}}$. We call this variant the maximum likelihood syncing, and it is the one
used in the experiments in Section~\ref{sec:eval}.

It is also important, for finite $n$, for the spy to know the message length $n$.
The simplest solution is to allow only messages of a fixed length, but it may be too restrictive.
One solution is to use the first $\left\lceil \log n_\text{max} \right\rceil$ bits to represent the length of the message that will be transmitted, where $n_\text{max}$ is
the maximum message length allowed.

