# An Automated End-to-End Side Channel Analysis Based on Probabilistic Model
## 3 Proposed Approach
### Change Point Detection
#### 3.2.1 Posterior Distribution
\[p(\mathbf{y}_{1:T}|r_{1:T},m_{1:K_{r}},\theta) =\prod_{k=1}^{K_{r}}\prod_{t=\tau_{k}}^{\tau_{k+1}-1}\mathcal{N}(y _{t};m_{k},\sigma^{2})\]4 \[p(\mathbf{y}_{1:T}|r_{1:T},m_{1:K_{r}},\theta) =\prod_{k=1}^{K_{r}}\prod_{t=\tau_{k}}^{\tau_{k+1}-1}\mathcal{N}(y _{t};m_{k},\sigma^{2})\]5 \[p(\mathbf{y}_{1:T}|r_{1:T},m_{1:K_{r}},\theta) =\prod_{k=1}^{K_{r}}\prod_{t=\tau_{k}}^{\tau_{k+1}-1}\mathcal{N}(y _{t};m_{k},\sigma^{2})\]6 \[p(\mathbf{y}_{1:T}|r_{1:T},m_{1:K_{r}},\theta) =\prod_{k=1}^{K_{r}}\prod_{t=\tau_{k}}^{\tau_{k+1}-1}\mathcal{N}(y _{t};m_{k},\sigma^{2})\]7  
where energy function of \(r_{1:T}\), \(H(r_{1:T})=\frac{V}{2\sigma^{2}(\sigma^{2}+V)}E_{r_{1:T}}+\gamma K_{r}\), \(E_{r_{1:T}}=\sum\limits_{k=1}^{K_{r}}\sum\limits_We detect the piecewise constants by computing the expectation of random variable \(r_{1:T}\),  
\[p(\mathbf{y}_{1:T}|r_{1:T},m_{1:K_{r}},\theta) =\prod_{k=1}^{K_{r}}\prod_{t=\tau_{k}}^{\tau_{k+1}-1}\mathcal{N}(y _{t};m_{k},\sigma^{2})\]8 \[p(\mathbf{y}_{1:T}|r_{1:T},m_{1:K_{r}},\theta) =\prod_{k=1}^{K_{r}}\prod_{t=\tau_{k}}^{\tau_{k+1}-1}\mathcal{N}(y _{t};m_{k},\sigma^{2})\]9 \[=\left(\frac{1}{2\pi\sigma^{2}}\right)^{-\frac{n}{2}}\exp\bigg{(} -\frac{1}{2\sigma^{2}}\sum_{k=1}^{K_{r}}\sum_{t=\tau_{k}}^{\tau_{k+1}-1}(y_{t} -m_{k})^{2}\bigg{)}. \tag{10}\]0  
where \(r_{1:T}\) is a true mean of \(r_{1:T}\) and \(r_{1:T}\) is an Monte Carlo estimate of \(r_{1:T}\) when \(r_{1:T}^{s}\sim p(r_{1:T})\). The last part holds when \(n\to\infty\). Instead of generating samples from the intractable posterior distribution \(p(r_{1:T}|\mathbf{y}_{1:T},\theta)\), we propose a function from which is easy to draw samples, namely proposal function(Metropolis-Hastings, Algorithm 1). We can think of two proposal functions regarding the property of change point detection problem. Given one sample, one of change points can be popped and two segments are merged or one change point is born and segment is split. Either case, this is reverting \(r_{t}\), \(0\to 1\), or \(1\to 0\). The other proposal function is a swap between \(0\leftrightarrow 1\). ```
procedureMH(\(p(\cdot),q(\cdot),r_{1:T}^{0},n\))\(\triangleright\) posterior, proposal and initial sample, number of samples for\(s=1,2,\cdots,n\)do \(r_{1:T}^{*}\sim q(r_{1:T}^{*}|r_{1:T}^{s-1})\) \(\alpha\leftarrow\frac{p(r_{1:T}^{*}|q(r_{1:T}^{*}|r_{1:T}^{*})}{p(r_{1:T}^{*}) q(r_{1:T}^{*}|r_{1:T}^{*})}\) \(a\leftarrow\min(1,\alpha)\) \(u\sim\mathcal{U}(0,1)\) if\(u<a\)then \(r_{1:T}^{s}\gets r_{1:T}^{*}\) else \(r_{1:T}^{s}\gets r_{1:T}^{s-1}\) return\(r_{1:T}^{1},r_{1:T}^{2},\cdots,r_{1:T}^{n}\)
```  
**Algorithm 1** Metropolis Hastings  
The proposal function for MCMC is succession of reverting and swapping with probability of  
\[q(r_{1:T}^{*}|r_{1:T})= \begin{cases}\frac{1}{T},&\text{if revert}\\ \frac{1}{K_{r}(T-K_{r})},&\text{if swap.}\end{cases}  \tag{17}\]  
This proposal probability is reducible, when calculated in Metropolis-Hastings, to  
\[\alpha=\frac{p(r_{1:T}^{*})q(r_{1:T}^{s-1}|r_{1:T}^{*})}{p(r_{1:T}^{s-1})q(r_ {1:T}^{*}|r_{1:T}^{s-1})}=\frac{p(r_{1:T}^{*})}{p(r_{1:T}^{s-1})}, \tag{18}\]  
since in reverting case the probability only depends on the length of the sample and in swapping case the number of change points does not change (\(K_{r^{s-1}}=K_{r^{s}}\)). Figure 3 shows the \(r_{1:T}\) obtained from MCMC section. However this model only detects the piecewise constants, so non-constant parts (i.e., drastic changes) are all high in probability of being change points.