learning_results.tex 5.54 KB
Newer Older
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
1
2
3
\section{Learning results} \label{sec:result}
\newcommand{\dk}{\emph{k}}
We use the setup described in Section~\ref{sec:setup} to learn models for OpenSSH, BitVise and DropBear SSH server implementations. 
4
OpenSSH represents the focal point, as it is the most popular implementation of SSH (with over 80 percent of market share in 2008~\cite{Albrecht2009Plaintext}) 
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
5
6
7
8
and also, the default server for many UNIX-based systems. DropBear is an alternative to OpenSSH designed for low resource
systems. BitVise is a well known proprietary Windows-only SSH implementation. 

In our experimental setup, the {\dlearner} and {\dmapper} were running in a Linux Virtual Machine. OpenSSH and DropBear were 
Paul Fiterau Brostean's avatar
updated    
Paul Fiterau Brostean committed
9
learned over a localhost connection, whereas BitVise was learned over a virtual connection with the Windows host machine. 
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
10
11
12
Certain arrangements had to be made including the setting of timing parameters to fit each implementation.

OpenSSH was learned using a full alphabet, whereas DropBear and BitVise were learned using a reduced alphabet. Both versions of
13
the alphabets are described in Subsection~\ref{subsec:alphabet}. The primary reason for using a reduced alphabet was to reduce learning times. 
14
15
16
17
18
19
20
21
22
23
24
25
Most inputs excluded were inputs that either didn't change behavior (like \textsc{debug} or \textsc{unimpl}), or that proved costly time-wise,
and were not critical to penetrating all layers. A concrete example is the user/password based authentication inputs (\textsc{ua\_pw\_ok} and 
\textsc{ua\_pw\_nok}). It would take the system 2-3 seconds to respond to an invalid password, perhaps in an attempt to thwart brute force attacks. 
By contrast, public key authentication resulted in quick responses. The \textsc{disconnect} input presented similar
challenges, particularly for BitVise. 

%Not only that, but failed password authentication
%attempts are also likely to trigger security mechanisms that would block subsequent authentication attempts. While this is 

%As an example, \textsl{ua\_pw\_ok} contours the same behavior as \textsl{ua\_pk\_ok}. But while authenticating
%with a public key was done quickly, authenticating with a username/password proved time consuming (it would take the system 2-3 seconds to respond to 
%invalid credentials \textsl{ua\_pw\_ok}). The \textsl{disconnect} proved expensive in a similar way.
Paul Fiterau Brostean's avatar
updated    
Paul Fiterau Brostean committed
26
27

For testing, we used random and exhaustive variants of testing algorithm described in 
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
28
29
30
31
32
\cite{SMJV15}, which generate efficient test suites. Tests generated comprise an access sequence, a middle section of length {\dk} and a 
distinguishing sequence. The exhaustive variant for a set {\dk}, generates tests for all possible middle sections and all states. Passing all tests provides some notion of confidence,
namely, that the learned model is correct unless the (unknown) model of the implementation has at least {\dk} more states. The random variant produces tests
with randomly generated middle sections. No formal confidence is provided, but past experience shows this to be more effective at finding counterexamples since {\dk}
can be set to higher values. We executed a random test suite with {\dk} of 4 comprising 40000 tests for OpenSSH, and 20000 tests for BitVise and DropBear. 
33
We then ran an exhaustive test suite with {\dk} of 2 for for all implementations. 
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
34
35
36
37
38
39
40
41
42
43
44
45
46

Table~\ref{tab:experiments} describes the exact versions of the systems analyzed together with statistics on learning and testing, namely:
(1) the number of states in the learned model, (2) the number of hypotheses built during the learning process and (3) the total number of 
learning and test queries run. 


 \begin{table}[!ht]
\centering
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
{\centering{\textbf{SUT}}} & \textbf{States} & \textbf{Hypotheses }  & \textbf{Num. Queries} \\ \hline  %& \textbf{Tests to last Hyp.}			& \textbf{Tests on last Hyp.} \\ \hline
OpenSSH 6.9p1-2            & 31              & 4               			 & tbc                    \\ %& 1322      						& 50243         \\
BitVise 7.23               & 65              & 15              			 & tbc                    \\ %& 9549   							& 65040         \\
Paul Fiterau Brostean's avatar
Files    
Paul Fiterau Brostean committed
47
DropBear v2014.65          & 17              & 2               			 & tbc                    \\ \hline %& 15268  							& 56174        \\
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
48
49
50
51
52
53
54
\end{tabular}
\caption{Statistics for learning experiments}
\label{tab:experiments}
\end{table}


The large number of states is down to several reasons. First of all, some systems exhibited buffering behavior. In particular, BitVise would queue
55
56
57
58
59
60
responses for higher layer inputs sent during key re-exchange, and would deliver them all at once, after the exchange was done. Re-exchanging keys (rekey-ing) was also
a major contributor to the number of states. In states permitting rekey, following the sequence of transitions comprising the rekey should lead back to the starting state. This 
leads to 2 additional rekey states for every state permitting rekey. A considerable number of states were also added due to {\dmapper} generated outputs such as \textsl{ch\_none} or \textsl{ch\_max}, outputs which signal that no channel is open or that the maximum number of channels have been opened. 

%Figure~{fig:sshserver} shows 

Paul Fiterau Brostean's avatar
Files    
Paul Fiterau Brostean committed
61
62
63
64
%To give a concrete example, the {\dmapper} on every \textsl{ch\_open} saves a channel identifier and sends
%a corresponding message to the {\dsut}. If \textsl{ch\_open} is called again, the {\dmapper} responds with a \textsl{ch\_max}. The channel identifier is removed 
%by a \textsl{ch\_close} input leading to pairs of  identical states with and without the channel identifier, even in states where channels are not relevant (like for example states prior to authentication). 

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
65