% -*- Mode: LaTeX -*-
%
% $Header: /home/gene/library/website/docsrc/sca/RCS/sca.tex,v 395.1 2008/04/20 17:25:48 gene Exp $
%
%  Copyright (c) 2006 Gene Michael Stover.  All rights reserved.
%

\documentclass{article}
\bibliographystyle{plain}
% \usepackage{html}
\input{/Users/gene/website/gg.texinc}

%
% Insert into the navi bar links to my personal Web page.
%
% \input{../navi.texinc}

%%%
%%% Commands
%%%

%%%
%%% Content begins
%%%

\begin{document}

\title{Algorithm for finding hosts which provide a UDP-based
service on a large network}
\author{gene m. stover}
\date{created Friday, 2006 January 13 \\
updated Tuesday, 2006 January 17}
\maketitle

{\em \small Copyright copyright {2006} Gene Michael Stover. All rights reserved. Permission to copy, store, \& view this document unmodified \& in its entirety is granted.}

\tableofcontents

\section{What is this?}

{\em As of Monday, 2006 January 16, this is almost finished.  I'd like
to do the SNMP \& CIFS examples before I declare it complete.}

I describe an algorithm which finds hosts which provide a
UDP-based service.  The algorithm is fast; it can scan the
10.x.y.z network in about 2.5 hours if you have enough
memory \& there are few providers of the service.  (The
algorithm's run time increases as the number of providers
increases.)

The algorithm allows you to specify the UDP-based service.
It does not know anything of the service.

The algorithm produces short bursts of UDP traffice, but there are
significant pauses between the bursts.

The algorithm uses just one thread.

The algorithm does not contain any stealth features.

I have implemented the algorithm in a command line program
which is licensed under the terms of the Gnu General Public
License.  The source code is available for download.

\section{Inputs}

The inputs to the algorithm are:

\begin{itemize}

\item The UDP port number for the desired service.

\item A message to send to hosts \& to which service
  providers will reply.  The algorithm treats the
  message as opaque data; it does not interpret the
  message or the replies.  You must create a message which
  is appropriate for the service that interests you.

\item An I/O timeout duration {\em T}, such as 10 seconds.

\item A list of Internet addresses (IP addresses) to
  search.

\end{itemize}

\section{Output}

The algorithm produces a list of the IP addresses of the
hosts which responded to the message.

I assume the list of IP addresses is available on standard
input ({\tt stdin}).

\section{The Algorithm}

The algorithm uses the unix {\tt select} (2) system call.
In the pseudocode here, I'll express that as ``wait for an
event on the socket''.

\begin{enumerate}

\item Create a UDP socket {\em s}.

\item Until there are no more addresses to scan

   \begin{enumerate}

   \item Load IP addresses into a {\em list} in memory.
   Load as many as will fit, but it's okay if they don't all
   fit.

   \item Until the {\em list} is empty

      \begin{enumerate}

      \item Wait for an event on socket {\em s} with timeout
      {\em T}.  If we have not sent to all of the {\em
      list}, we are interested in input \& output.  If we
      have sent to all of the {\em list}, we are only ready
      for input.

      \item If input is waiting on {\em s}, read it with
      {\tt recvfrom}.  Extract the sender's IP address \&
      print it.  Remove that IP address from the {\em list}.

      \item If {\em s} is ready for output \& we have not
      sent all of the {\em list}, send the message to the
      next IP address on the {\em list}.

      \item If there was a timeout (i.e., we were only
      interested in input, \& there was none), clear the
      {\em list}. 

      \end{enumerate}

   \end{enumerate}

\item Exit

\end{enumerate}

\section{How it works}

Imagine asking the algorithm to scan a bunch of IP
addresses, \& it just happens that none of the hosts
provide the service that interests you.  As the algorithm
sends the message to the hosts, none of them reply.  So,
{\em T} seconds after sending the final address, the
algorithm times out, clears the list, \& announces that it's
done \& none of the hosts are service providers.

Run time for that instance is {\em T} seconds plus the
number of seconds to send all the UDP messages.

Now imagine that one of the IP addresses is for a host that
does provide the service.  Then the algorithm will send many
of the IP addresses before receiving a reply from that
host.  It will print that host's IP address, remove it from
the list, \& begin the process again.  But this time, the
process is the case in which none of the hosts are
providers.  So it's the run time from the ``no providers''
case (a little over {\em T} seconds), plus the number of
seconds for the one host to reply, which will be one or two
seconds in practice, \& just under {\em T} seconds in the
worst case.  So the run time will be roughtly $T + 2$
seconds in practice or $2 T$ seconds in the words case.

As you imagine cases in which more \& more of the hosts are
service providers, it just increases the number of
iterations through the list.  Each iteration removes one IP
address from the list, so that it eventually degeneratese to
the case in which none of the hosts are providers.

\section{Example: echo}

The echo service, which isn't used much (probably for
security reasons), is on UDP port 7.  You send it a line, \&
it sends you that same line.  The message to make echo reply
can be just about anything.  Here's the one I used:

\begin{verbatim}
$ cat src/echo.sca
hello, world
$ 
\end{verbatim}

I have echo running on one of my computers, at 10.1.0.5.
The generator I used generates all the 10.1.\verb|[01]|.{\em y}
addresses, preceeded by 128,000 others (which might be
routed over the Internet -- it's a test).  It finds 10.1.0.5.

\section{Example: daytime}

The daytime is an old one, like echo.  It's on port 13.  I
used the same generator as for the echo test.  I used a file
of one empty line for the message.  (Just about any file
would have worked.  As with echo, daytime does not examine
the payload it receives.)

I'm running daytime on 10.1.0.2.

\begin{verbatim}
$ bin/gen |bin/scan 13 src/daytime.sca >001.txt

MAX_OCTETS_IN_LIST is 1048576.
S_lst_len is 262144.
src/scan.c:159: Message contains 1 octets
src/scan.c:239: S_LoadLst: S_count is 131584. Last is 10.1.1.255.
sendto: Permission denied
src/scan.c:344: sendto (10.1.0.0) failed
sendto: Permission denied
src/scan.c:344: sendto (10.1.0.0) failed
src/scan.c:239: S_LoadLst: S_count is 0. Last is 0.0.0.0.$ 
$ cat 001.txt
10.1.0.2
$ 
\end{verbatim}

\section{Example: ONC RPC portmapper}

The portmapper service for ONC RPC is on port 111 (both TCP
\& UDP, but we're only scanning the UDP ports).

The only trick to scanning for the portmapper is that the
message is not obvious.  I looked through the
\verb|<rpc/*.h>|\ header files to figure out how to
construct a remote call to the portmapper.  Then I wrote
\htmladdnormallink{{\tt
    src/msg-portmapper.c}}{src/msg-portmapper.c}\ to
construct the message \& send it to {\tt stdout}.  The
message does not have to be perfect; it just needs to
motivate the portmapper to reply.

Here are the results of the run.  I used the same
generator as for the previous two examples.

\begin{verbatim}
$ bin/msg-portmapper >src/portmapper.sca
$ time bin/gen |bin/scan 111 src/portmapper.sca >001.txt

MAX_OCTETS_IN_LIST is 1048576.
S_lst_len is 262144.
src/scan.c:159: Message contains 56 octets
src/scan.c:239: S_LoadLst: S_count is 131584. Last is 10.1.1.255.
sendto: Permission denied
src/scan.c:344: sendto (10.1.0.0) failed
sendto: Permission denied
src/scan.c:344: sendto (10.1.0.0) failed
src/scan.c:239: S_LoadLst: S_count is 0. Last is 0.0.0.0.
real	1m4.705s
user	0m1.010s
sys	0m3.390s
$ cat 001.txt
10.1.0.2
10.1.0.5
$ 
\end{verbatim}

You can see that I'm running the RPC portmapper service at
10.1.0.2 \& 10.1.0.5.\footnote{That means that 10.1.0.4 \&
10.1.0.9 have problems.  Oh well.}

\section{Example: SNMP}

To construct a message for SNMP, I used a remote
printer-controlling application to query a printer while I
had a network sniffer running.  The sniffer showed the forty
or so octets that the application sent to the printer in its
first transmission.  I typed those numbers into a Lisp expression
which dumped them as octets into the \htmladdnormallink{{\tt
    snmp.sca}}{src/snmp.sca}\ file.

SNMP is on port 161.

After that, I ran the scanner on a LAN which contains a
lot of SNMP devices, \& the scanner located most of them.
It worked better when the timeout was 60 seconds.

I won't show the results here because I'm writing this essay
at home, \& that network with all the SNMP devices is at a
customer's site.

\section{Example: CIFS}

%%%
%%%
%%%
\appendix

\section{Source Code}

The program which scans is
\htmladdnormallink{{\tt scan.c}}{src/scan.c}.

\htmladdnormallink{{\tt gen.c}}{src/gen.c}\ generates IP addresses from
some hard-coded data.  It's for testing or demo purposes.

\htmladdnormallink{{\tt counter.c}}{src/counter.c}\ is a simple UDP
service that can be helpful for tests or demos.

\htmladdnormallink{{\tt
msg-portmapper.c}}{src/msg-portmapper.c}\ generates the
message for scanning for the ONC RPC {\tt portmapper}
service.

\input{tmp/directory.tex}
\input{tmp/counter.tex}
\input{tmp/debug.tex}
\input{tmp/gen.tex}
\input{tmp/msg-portmapper.tex}
\input{tmp/scan.tex}
\input{tmp/this.tex}

\section{What about nmap?}

Yes, {\tt nmap} can scan like this.

I didn't use {\tt nmap} because my client needed code
which was unencumbered by the license agreement on
{\tt nmap}.

``Unencumbered by the GPL?  But you, yourself, slapped the GPL on
your own code?''  Yes, I did, \& since I'm the license-holder,
I can create a custom, non-GPL license for my client.

``If the user installed {\tt nmap} separately, wouldn't
that allow your client's software to work with {\tt nmap}
without itself being GPLed?'' I believe it would.

``So could you do that?  Could you require the user
to install {\tt nmap} himself?'' No.

\bibliography{/Users/gene/website/only}

\end{document}
% --- end of file ---
