Nmap Development mailing list archives
[NSE] A Lua implementation of NSE
From: "Patrick Donnelly" <batrick.donnelly () gmail com>
Date: Tue, 6 Jan 2009 23:06:50 -0700
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
Current thread:
- [NSE] A Lua implementation of NSE Patrick Donnelly (Jan 06)
- Re: [NSE] A Lua implementation of NSE Brandon Enright (Jan 07)
- Re: [NSE] A Lua implementation of NSE David Fifield (Jan 15)
- Re: [NSE] A Lua implementation of NSE--detailed review David Fifield (Jan 16)
- Re: [NSE] A Lua implementation of NSE--detailed review Patrick Donnelly (Jan 17)
- Re: [NSE] A Lua implementation of NSE--detailed review Patrick Donnelly (Jan 17)
- Re: [NSE] A Lua implementation of NSE--detailed review David Fifield (Jan 18)
- Re: [NSE] A Lua implementation of NSE--detailed review Patrick Donnelly (Jan 20)
- Re: [NSE] A Lua implementation of NSE--detailed review Patrick Donnelly (Jan 17)
- Re: [NSE] A Lua implementation of NSE Ron (Jan 17)
- Re: [NSE] A Lua implementation of NSE--chance for deadlock David Fifield (Jan 18)
- Re: [NSE] A Lua implementation of NSE--chance for deadlock Patrick Donnelly (Jan 20)
- Re: [NSE] A Lua implementation of NSE--chance for deadlock David Fifield (Jan 18)