[NSE] A Lua implementation of NSE

["Patrick Donnelly" <batrick.donnelly () gmail com>]

Before I begin, I want to stress that when I say "thread", I am
referring to Lua's threads which are used to facilitate NSE's
parallelism with scripts. Also, I use coroutines and threads
interchangeably.

The code for this implementation can be accessed at:
svn://svn.insecure.org/nmap-exp/patrick/nse-lua

This is a very long post about this branch. I don't expect anyone to
read all of it, just what interests you. If you think something being
offered as new functionality would be useful or if you like the way
something was (re)implemented, please, speak up. If you have a related
problem with NSE you would like addressed, it may be easy to add now,
so again, please, speak up. Whether or not this is used entirely
depends on its reception. This project originally started out as an
experiment and has turned out well.

== Preface ==

For the last couple months I have been working on an implementation of
NSE in Lua. There were several motivating factors for doing this.
Principally, the code base could be dramatically simplified (in one
respect, lines of code). Also, with the switch to Lua comes huge
returns in maintainability, flexibility, and extendability. The code
itself is easier to understand and follow largely due to Lua's
expressiveness when compared to C++. The switch to Lua also removes
most of the barrier a script developer confronts when trying to
understand how his script is eventually run. Instead of needing to
know two languages he only need know one.

Of course all these statements sound very subjective. Besides looking
at the code yourself, I'll try to quell your skepticism with an
example of how the Lua implementation allows for easier extendability.

When I first started, I had not planned to add a library which allows
a script to interface with NSE (Discussed in Section IV below). Later
on, Ron and Brandon privately pointed out a problem that could not be
solved by scripts alone: they needed to be able to have functions
called that ran when a script ended for any reason (errors in
particular). They excluded a complicated hack that monitored the
garbage collection of objects (not entirely fool-proof) which I
posited could solve their problem. So, I began working on a library
scripts could use to control aspects of execution. To solve their
specific problem I added a close function NSE calls on each thread
when it finishes executing for any reason. This close function calls
all the function handlers the script added, first the most recent,
last the latest (a stack). The handlers are added and removed with
nse.push_handler and nse.pop_handler, respectively.

The total difference in lines of code ended up being just _16_ lines.
In order to make that number more meaningful, to do the same in the
current implementation (in C++) would require the maintaining of a
table per thread in the registry for the stack, a mechanism to
distinguish a child thread from the current NSE thread (perhaps the
script is using a coroutine?), two functions bound to Lua in some
namespace and have access to the current thread_record, and a
procedure to call all the script's close handlers. The push and pop
functions alone would easily require at least 10 lines each (Lua C
API). It quickly becomes clear that allowing Lua to absorb the
complexity of managing itself (that is, script threads) is optimal. In
this case, Lua really shines as a glue language, something it is very
well known for.

In all, the switch to Lua does not bring any sweeping changes to how
scripts are run, just provides a easily maintained platform where it
is very simple to add functionality and to obtain information.
However, some changes from the old system do exist and are described
in Sections II - V.

===

I divided some of the new features or discussion into the following Sections:

I. NSE Initialization and How it Works
II. Host Timeout Management
III. Yields propagated up to parent thread back to NSE
IV. The NSE API
V. Host and Port Userdata


I. NSE Initialization, Scanning, and How it Works

When Nmap starts, NSE now immediately begins all initialization
including the loading of scripts chosen by the --script switch. Any
problems in loading NSE will stop Nmap before any host scanning
begins. Besides reducing headache when a script fails to load or a
missing library is not found, this has the advantage of separating the
invariant set of scripts that will run for all host groups.

NSE is started via the open_nse (and closed using close_nse) procedure
in nse_main.cc. This function begins by opening all standard Lua
libraries and adding all Nmap standard C libraries to package.preload
(to be required in nse_main.lua). Next nse_main.lua is loaded and
called with the private nse library (different from the one discussed
in Section IV) and the array of rules (--script) are passed as
arguments. The private nse library is used to access some
functionality needed through C such as keyWasPressed() or
nsock_loop().

When run, nse_main.lua begins by saving local references to all global
functions it needs to lower access time and so scripts cannot
accidentally or purposefully change them. Following this, it sets the
package.path to include the nselib directory and require all the C
libraries Nmap scripts use (purely to immediately load them into the
global namespace). NSE then replaces coroutine.resume and
coroutine.wrap to propagate yields NSE initiates up to the parent
script (discussed in Section III). NSE loads all arguments passed via
--script-args and exits if they cannot be loaded. Finally, all scripts
chosen by --script or -sC ("default") are loaded immediately. If a
script cannot be loaded NSE will throw an error and cause Nmap to
exit. Scripts are loaded into a Script class where all information
relevant to a script is saved including the filename, id, file
closure, hostrule, categories, etc. Different from the C++ NSE, strict
type checking is enforced for all required script variables. For
example, the categories array is asserted to be an array of strings
(not simply a table).

nse_main.lua ends by returning a function that scans a host group. NSE
saves this function in the Registry for when NSE actually begins
scanning. This ends the initialization stage.


When NSE (the returned function by nse_main.lua) is used to scan a
host group, a new nse library is created for scripts (replacing the
old one). Functions that provide access to information in the current
host group are created dynamically making use of Lua's lexical scoping
and upvalues. This is perhaps the most powerful aspect of the new
implementation. It is extremely easy to create a function that allows
scripts to access the engine's (local) internals in a safe and elegant
manner. For example, nse.hosts allows scripts to iterate through all
the hosts in the current host group.

Immediately afterwards, NSE begins to test hostrules and portrules
against every Script that was chosen during initialization. If a
thread is created (the rule function existed and returned true), then
the thread is placed in its corresponding runlevel table. Finally for
each runlevel, in sorted order of course, NSE passes the runlevel
group to a run function which handles the actual scanning.

The run function creates running and waiting queues which contain
threads ready to be run and threads waiting to be moved to running.
Again, NSE makes use of Lua's lexical scoping to create functions that
manipulate the values in the running and waiting queues. Particularly,
the function (used by C), WAITING_TO_RUNNING, moves a thread from the
waiting queue to the running queue.

Finally, the scanning begins. While any thread exists in the running
or waiting queues, NSE loops: NSE starts by calling nsock loop to
perform any pending network operations, removes all threads timed out
from the waiting queue, and finally runs all threads in the running
queue. Running the threads in the running queue is very similar to the
current system except for more verbose debug output and the engine
more safely handles coroutine manipulation. The debug output is very
similar to what was recently added in revisions 11656-11661.



II. Host Timeout Management

Before, NSE would immediately start the time out clocks for all hosts
in the current runlevel group and stop the clock only when no other
thread exists for that host. A problem arises when a thread is waiting
to acquire sockets or is blocked on a mutex and is not technically
running (indirectly or otherwise) against the host. The target should
not be charged time when none of its threads are working.

This implementation of NSE keeps a table of threads for each host.
Immediately before a thread begins executing, the thread is removed
from its hosts table. A function that yields the thread, like a mutex
function or socket function, will signal to NSE that the thread's host
should continue to be charged time. NSE will again add the thread to
the host's table if it should be charged. Then, if the host's table is
empty, the host time out clock will be stopped. Lua-style pseudocode
for the algorithm:

while not (EMPTY(running) and EMPTY(waiting)) do -- while running or
waiting contains threads
  for thread in running do
    hosts[thread.host][thread] = nil;
    thread.host:startTimeOutClock();
    -- run the thread
    if charge_time then hosts[thread.host][thread] = true; end
    if EMPTY(hosts[thread.host]) then thread.host:stopTimeOutClock() end
  end
end

These are the following ways a thread may yield and whether its host
will still be charged time.

o A thread that was unable to acquire a socket connection (because the
quota for threads with open sockets is full) will not be charged time
it is suspended.
o A thread blocked on a mutex or condition variable (see nse.condvar)
will not be charged time.
o A thread blocked on a network operation is charged time.

A C function which yields the thread must signal whether the host
should continue to be charged time. It does so when it calls
nse_prepare_yield(lua_State *L, int charge). nse_prepare_yield is
further documented in Section III.



III. Yields propagated up to parent thread back to NSE

When a script thread yields, NSE resumes operation and checks the
status and return values of the thread. When a thread uses its own
coroutines for collaborative multithreading, a function that yields
the thread expecting NSE to resume operation will fail. Specifically,
the callback mechanisms believe the thread it yielded earlier was
actually one being run by NSE (when in fact it was a child coroutine
of the script thread). When it attempts to move this child coroutine
into the running threads for NSE using process_waiting2running, the
procedure silently fails because it cannot find the thread in the
waiting queue (only threads NSE creates are ever in the waiting and
running queues). Consider the following script:

<file = "cotest.nse">

author = "patrick"
description = "coroutine test!"
categories = {"default"}

require "shortport"

portrule = shortport.port_or_service(22, "ssh")

function a (host, port)
  local try = nmap.new_try();
  local socket = nmap.new_socket();
  try(socket:connect(host.ip, port.number));
  return "connected!";
end

function action (host, port)
  local co = coroutine.create(a);
  print(coroutine.resume(co, host, port));
  print(coroutine.resume(co));
  return "done";
end
</file>

If you run this in the main Nmap branch you will get the following output:

<output>
batrick@waterdeep:~/nmap/svn/nmap$ ./nmap --script cotest.nse localhost

Starting Nmap 4.76 ( http://nmap.org ) at 2008-12-30 03:52 MST
true
false   nil
Interesting ports on localhost (127.0.0.1):
Not shown: 998 closed ports
PORT     STATE SERVICE
22/tcp   open  ssh
|_ cotest: done
3690/tcp open  unknown

Nmap done: 1 IP address (1 host up) scanned in 0.14 seconds
</output>

The problem is a little subtle. When the script thread resumes its
child coroutine for the first time, the child yields in the call to
socket:connect(host.ip, port.number). You can see the printed, yielded
values from socket:connect() in the first line of output (the single
line, "true", indicating there were no errors running the coroutine
and no values were yielded). Next, the script thread again resumes the
child. Except, the return values from connect() are not passed to try
but instead nothing is passed; the call to coroutine.resume did not
pass any new arguments. The try function will raise an error on the
second argument (nil) because the first value (also nil) casts to
false. The printed values in the script thread are thus "false nil".
Remember that an error (exception) can be any Lua type, not just a
typical string.

To solve this problem I have modified the coroutine.resume and
coroutine.wrap functions to propagate the yield up to the parent
thread so NSE may assume control, but only when NSE yields the thread.
In order for NSE to distinguish between normal returned (or yielded)
values from a script's coroutine, a special value, NSE_YIELD (a
table), is yielded whenever NSE yields the thread. This table also
contains (for now) two values at indices 1 and 2 which are useful for
tracking resources for the threads and establishing the base (parent)
thread for callbacks in C.

There are two procedures that are used to facilitate the use of NSE_YIELD:

int nse_prepare_yield (lua_State *L, int charge);
void nse_restore (lua_State *L, int index, int number);

nse_prepare_yield is used to place the value NSE_YIELD on the stack,
to indicate to NSE that the thread's host should be charged time
(towards a timeout) while the thread is suspended, and to return an
integer index that is passed to nse_restore when the thread is ready
to be resumed. The value left on the stack, NSE_YIELD, must be yielded
by the caller.

nse_restore is passed the integer returned by nse_prepare_yield and
the number of arguments on the stack of L that should be passed to the
thread you are resuming. L is allowed to be the thread you intend to
resume.

Now, if you run cotest.nse in the Lua implementation you receive the
following output:

<output>
batrick@waterdeep:~/nmap/svn/patrick/nse-lua$ ./nmap --script
cotest.nse localhost

Starting Nmap 4.76 ( http://nmap.org ) at 2008-12-30 03:55 MST
true    connected!
false   cannot resume dead coroutine
Interesting ports on localhost (127.0.0.1):
Not shown: 998 closed ports
PORT     STATE SERVICE
22/tcp   open  ssh
|_ cotest: done
3690/tcp open  unknown

Nmap done: 1 IP address (1 host up) scanned in 0.14 seconds
</output>

As you can see, the first resume actually establishes a connection.
NSE yielded and resumed the parent script thread in the background so
the connect function's results are properly returned and passed to
try.

To allow a script to actually have multiple child threads managed by
NSE, so the parent may do other work during a child's network
operations, there exists the function nse.new_thread discussed in
Section IV.



IV. The NSE API

The NSE API is accessible in the nse namespace. The following
functions are available:

== nse.hosts ==
This function is an iterator you use in a generic for loop like so:

for i, host in nse.hosts do
  print(host)
end

Notice the function is not called like pairs [3] would be for a
table.The iteration allows you to have access to all the hosts that
are being processed in the current host group.  Host and port userdata
are discussed in Section V.

== nse.condvar(object) ==
This function allows the script to wait on a condition until another
thread signals or broadcasts the condition (similar to POSIX Condition
Variables). The function is particularly useful for a thread which
launches multiple new threads that it must monitor (see
nse.new_thread).

It is similar to nmap.mutex in that it returns a function that is
associated with the unique object. The object may be any Lua data type
except nil, booleans, and numbers. The following options may be passed
to this function: "wait", yields the current thread until another
thread signals it should run again; "signal", moves a thread waiting
on the condition variable to the NSE running queue; and "broadcast",
moves all waiting threads waiting on the condition variable to the NSE
running queue. Example usage:

local cv = nse.condvar("my unique id");
cv "wait";  -- waits for another thread to awaken it, signaling the condition

This function is different from nmap.mutex in that it allows a thread
to wait unconditionally (a mutex must be currently locked for the
thread to wait). The primary use of this function will be to
coordinate with child threads created by nse.new_thread.

== nse.new_thread(func, ...) ==
A coroutine run manually by a script thread will propagate the yield
through the parent back to NSE. To avoid this, you may use
nse.new_thread to create a thread which is autonomous from the parent.

The function launches a new thread (coroutine) that is managed by NSE.
It inherits the host and port of the parent thread but these values
are not passed to func. Instead the extra parameters to new_thread are
passed. All errors are ignored and return values discarded by NSE.

== nse.push_handler(func) ==
This function pushes func on a handler stack. If the thread ends
normally or aborts due to an error, all functions on the handler stack
are called from the top of the stack down.

== nse.pop_handler() ==
This function pops a function from the thread's handler stack.

== nse.get_host() ==
This function returns the host userdata associated with the script
thread. See Section V for information on this userdata.

== nse.get_port() ==
This function returns the port userdata associated with the script
thread. See Section V for information on this userdata.



V. Host and Port Userdata

NSE uses host and port userdata to easily, and safely, interface with
Nmap's internal classes that represent these objects. A Script may
access its host or port userdata by using the calls nse.get_host and
nse.get_port, respectively. When a new host group is processed,
new_host (lua_State *L, Target *target) is called for each target in
the group. This host userdata is simply a double pointer (pointer to a
pointer) for the Target. The methods for the userdata provide an easy
way to call the methods of the Target Class (documented later). Once
the userdata is made, every port for the host that is in the state
PORT_OPEN, PORT_OPENFILTERED, PORT_UNFILTERED is created (once) using
new_port(lua_State *L, Target *target, Port *port). These ports are
saved in a table, TARGET_PORTS, in the target userdata's environment
[1]. Host and Port userdata can be used as unique objects representing
the host or port.

While the file nse_hosts.cc is relatively large (440 lines) in
comparison to other parts of NSE, the way to add functionality (or
rather, bind more methods) to a target or port userdata is very
straightforward and headache free. As an example, the HostName
function for a Target:

static int HostName (lua_State *L)
{
  lua_pushstring(L, checktarget(1)->HostName());
  return 1;
}

Is simply two lines in the body of the function. Most of the functions
are similarly small. Macros are a big help in making it easier,
checktarget is defined as:

#define checktarget(i) (*((Target **) luaL_checkudata(L, (i), TARGETCLASS)))

What follows are the currently bound functions for each host and port
userdata. I have kept the unique capitalization most of the functions
had for those more familiar with Nmap's internals. I will keep the
descriptions short for brevity, most of the functions are just simple
bindings to the same function for a Host or Port. The comments and
documentation for those Target and Port class methods will yield the
more detailed information you may need.

== host:targetipstr() ==

Returns the targetipstr string for the host.

== host:NameIP() ==

Returns the NameIP string for the host (maximum 512 characters).

== host:HostName() ==

Returns the HostName string for the host.

== host:TargetName() ==

Returns the Target's name (rDNS) string.

== host:directlyConnected() ==

Returns whether the host is directly connected (nil, false, or true).

== host:MACAddress() ==

Returns the 6 byte (length) string containing the MAC address of the host.

== host:SrcMACAddress() ==

Returns the 6 byte (length) string containing the Source MAC address
of the host.

== host:deviceName() ==

Returns the device name string for the host.

== host:binaryIP() ==

Returns the 4 byte (length) string containing the binary
representation of the host's IPv4 address.

== host:binaryIPSrc() ==

Returns the 4 byte (length) string containing the binary
representation of the source IPv4 address.

== host:os() ==

Returns a table with up to 8 entries of operating system matches
(possibilities) or nil if no arbitrarily viable entries exist.

== host:timedOut() ==

Returns a boolean indicating if the host as timed out.

== host:startTimeOutClock() ==

Begins the time out clock if it is not already running.

== host:stopTimeOutClock() ==

Stops the time out clock if it is running.

== host:next_port(lastPort) ==

Similar to the Lua function next [2], this function returns only the
next port for the host. The first port is returned when lastPort ==
nil.

== host:ports() ==

Similar to the Lua function pairs [3], this function can be used to
return the iterator in a generic for loop to loop through all the
host's ports. Example usage:

for port in host:ports() do print(port:number()) end

== host:totable() ==

This simply uses all the methods for the host userdata to build a
table of the values typically passed to a script to represent the host
in its hostrule, portrule, and action functions.

== host:set_output(id, output) ==

This function sets the output for the id tag for the host. NSE uses
this method to set the output for a script.


The port userdata are privately held by each host userdata in its
environment table. They also have methods:

== port:number() ==

Returns the ports number.

== port:protocol() ==

Returns the port's protocol, either "udp" or "tcp".

== port:version() ==

Returns a table containing all information relevant to the port's
"version". This table is exactly what is in the port.version table
passed to the action function now (see NNS book for detailed
description).

== port:state() ==

Returns the port state string (e.g. "open").

== port:reason() ==

Returns the port's reason identifier.

== port:totable() ==

Similar to host:totable() but for ports. Creates a table exactly as is
needed for the portrule and action functions.

== port:set_output(id, output) ==

The method NSE uses to set the output information for a port.


[1] http://www.lua.org/manual/5.1/manual.html#2.9
[2] http://www.lua.org/manual/5.1/manual.html#pdf-next
[3] http://www.lua.org/manual/5.1/manual.html#pdf-pairs


I'm sure I may have under-described some functionality or changes and
people would like more explanation. Just ask and I'll try to oblige.

Looking forward to hearing people's thoughts!

-- 
-Patrick Donnelly

"One of the lessons of history is that nothing is often a good thing
to do and always a clever thing to say."

-Will Durant

_______________________________________________
Sent through the nmap-dev mailing list
http://cgi.insecure.org/mailman/listinfo/nmap-dev
Archived at http://SecLists.Org