Puzzle Corner

Ernest J. Friedman-Hill

(The first in an occasional series of articles)

The following puzzle was posted to the "Programming Diversions" forum by Stevie Kaligis on February 17, 2002.

Three men, A, B, C and their respective wives, Aw, Bw and Cw, were hunting in deepest Peru, when they came across a large river. Luckily there was one boat, however, it could only carry two people at the same time. Due to bitter jealousy, no woman could be left with another man unless her husband was present. How did they manage to cross the river?

A lively discussion ensued, in which some people actually tried to solve the problem.

Think for a minute about how you might solve this puzzle with a computer. Computers are good at brute force search, and so that's probably how you'd want to do it. Coding something like this in Java could be tricky and hard to understand; a rule-based language like Jess (See "http://herzberg.ca.sandia.gov/jess") would be better suited. Java is a rule engine and scripting environment written in Java; it complements, and integrates nicely with, existing Java software.

In this article, I'll show how to solve a logic puzzle like this one in Jess. We will indeed use search, but it will be a heuristically guided search, meaning that irrelevant parts of the search space will be cheaply pruned off and never explored -- making this far more efficient than a true brute-force search using a nested set of for loops.

Rule-based programming

Rule-based programming is declarative, meaning that you don't write down a precise list of instructions for the computer to follow, but rather concentrate on describing the problem, and allowing the computer to come up with the solution. The description in a rule-based language takes the form of rules; basically, things for the computer to do in a specific situation. The language runtime, called a rule engine, takes all the rules, all the data you supply, and applies the rules to the data according to the semantics of the language. It's a perfect arrangement for non-algorithmic problems -- problems you don't consciously know how to solve.

Declarative programming is powerful, but it's still uncommon enough that many people aren't familiar with it. Furthermore, the concepts that you need to express in declarative programming are different from those you deal with in everyday procedural programming, and this means that the language has to be rather different from Java. This has led to a widespread belief that they're difficult to learn or use, which really isn't true.

What it boils down to is that there are two kinds of rule-based languges in common use: powerful ones, and simple ones. The powerful ones tend to have more difficult syntax, and that scares some people off. Jess is one of the powerful ones, and so its syntax requires a bit of learning. I won't have enough space here to teach you everything about the Jess language, although I'll try to hit the high points. See the Jess web site or the book Jess in Action for more details. I will take the opportunity, though, to try to debunk the myth that the rule syntax is gratuitously hard to understand.

It turns out that this "Jealous husband problem" is not especially easy to solve in Jess. Here, by "not easy" I mean that the solution isn't very short -- it's about 300 well-commented lines of code. This will give us an opportunity to explore what's possible in Jess.

Data structures

Like any program, ours will need data structures. Since we're Java programmers, we'll use inheritance to express the idea that men and women are categories of person:

(deftemplate person
  "One of the people who is travelling."
  (slot name))

(deftemplate man extends person
  "A male person"
  (slot wife))

(deftemplate woman extends person
  "A female person"
  (slot husband))

Jess templates are very much like Java classes, and slots are like JavaBeans properties -- member variables with getX() and setX() methods. Since we're going to do a search of possible solutions, we'll also need a template to represent one individual node in the search tree. A "state" will represent a moment in time where the boat is on one shore or another, and all the people are out of the boat.

(deftemplate state
  "One step along the path to the solution."
  (slot search-depth)
  (slot parent)
  (slot locations)
  (slot last-move))

The "locations" slot will hold a Java HashMap with people's names as the keys, and their locations as the values, so that we know where everybody is at each point in the search tree. The "search-depth" and "parent" slots will keep track of the tree structured relationships between the states, and the "last-move" slot will record which of our intrepid travellers were in the boat in the time leading up to this state.

Then we just define all the people:

(deffacts MAIN::people
  "All the people involved in the problem."
  (man (name A) (wife Aw))
  (man (name B) (wife Bw))
  (man (name C) (wife Cw))
  (woman (name Aw) (husband A))
  (woman (name Bw) (husband B))
  (woman (name Cw) (husband C)))

This construct creates a bunch of objects, or as they're called in Jess, facts. A fact is an instantiation of a template, just as an object is an instantiation of a class. There's one fact for each person mentioned in the problem statement.

Legal moves

Here's how we're going to solve this problem: we'll start from an initial state with all the people on one side of the river. Then we'll create new "state" facts to represent a superset of the legal moves from that state. We'll refine the superset until only legal moves are left. Then we'll repeat the process starting from the new set of states. When a state is created where all the people are on the other side of the river, that's a solution to the problem. We'll print it out along with all the states that led to it, then delete this whole branch of the search tree.

Jess is a rule-based language, so we'll generate the valid moves with rules based on the problem statement. All these rules will make heavy use of utility functions specific to this problem, which we'll look at a little later on.

The complete solution is available here. You'll need to download the trial version of Jess from the web site to run the problem.

A rule consists of two main parts, basically an "if" part and a "then" part. The "if" part comes first and consists of a list of patterns. Each pattern is used to select matching facts from the collection of available facts. A pattern

  (man (name ?n))

means this rule should apply to all men, and furthermore, we want to use the variable ?n to mean this man's name (variables in Jess start with a '?'.) If you were reading the rule out loud, you'd say "There's a man, let his name be ?n".

Patterns that start with test are Boolean function calls that can further qualify where the rule applies.

The second main part of each rule is the "then" part; there's an arrow => in between the two parts. The "then" part can contain arbitrary Jess code -- the Jess language includes a complete procedural language as well, and it can work with Java objects and call Java methods, too.

The first rule, move-alone, says that at any time, a person who, in some given state along the search tree, is on the same side of the river as the boat can take the boat and move across the river, creating a new state. Note that a "person" pattern can match either a man or a woman fact, because of their inheritance relationship, just like passing arguments to a method in Java.

(defrule MAIN::move-alone
  "Any person on the same shore as the boat
   can move alone across the river."

  ;; If there is a person named ?n
  (person (name ?n))

  ;; And there is a state
  ?state <- (state)

  ;; And in that state, the person is on the same shore
  ;; as the boat
  (test (same-shore-as-boat ?n ?state))
  =>
  ;; then generate a new state where they've moved
  ;; across the river
  (move-alone ?n ?state))

The next rule says that two people of the same gender, who again, are in the same location as the boat, can use it to cross. The "~" symbol means negation, and the "&" symbol means logical "and," so "?n2&~?n1" means "this person's name, let's call it ?n, is different from ?n1." If these person facts were Java objects, the same code might look something like

Person p1 = getOnePerson();
Person p2 = getOnePerson();
String n1;
String n2;
if (p1 != null && p2 != null &&
  !(n1 = p1.getName()).equals((n2 = p2.getName())))
   ...
}

(defrule MAIN::move-together-same-gender
  "Any two people of the same gender,
   both on the same shore as the
   boat, can move across the river."

  ;; Given one person
  ?p1 <- (person (name ?n1))

  ;; and another person with a different name...
  ?p2 <- (person (name ?n2&~?n1))

  ;; but the same gender
  (test (same-gender ?p1 ?p2))

  ;; (considering their names in alphabetical order)
  (test (alphabetical-order ?n1 ?n2))

  ;; and in some state
  ?state <- (state)

  ;; one is on the same shore as the boat
  (test (same-shore-as-boat ?n1 ?state))

  ;; and the other is on the same shore as the first
  (test (same-shore ?n1 ?n2 ?state))
  =>

  ;; then make a new state where they have crossed together.
  (move-together ?n1 ?n2 ?state))

The next rule says that a woman and her husband can cross together. I'm not going to comment this one as heavily -- I think you get the idea by now:

(defrule MAIN::move-together-married-couple
  "Any married couple, both on the same shore as the boat,
   can move across the river."
  (man (name ?n1))
  (woman (name ?n2) (husband ?n1))
  ?state <- (state)
  (test (same-shore-as-boat ?n1 ?state))
  (test (same-shore ?n1 ?n2 ?state))
  =>
  (move-together ?n1 ?n2 ?state))

There are two more path-generation rules. They're in a different Jess module, and it's an auto-focus rule. Together, this makes each one something like a background thread: it jumps in and does its business whenever it's needed, but otherwise it stays out of the way.

This rule enforces the "bitter jealousy" constraint by retracting states where a husband and wife are separated, but the wife and another man are on the same shore:

(defrule CONSTRAINTS::unmarried
  "A woman and a man not her husband cannot both be
  on the same shore, unless the husband is also present."
  (declare (auto-focus TRUE))

  (woman (name ?wife) (husband ?husband))
  (man (name ?husband))
  (man (name ?other-guy&~?husband))
  ?state <- (state)

  ;; The husband and wife are not on the same shore,
  ;; but the wife and the other guy are.
  (test (and (not (same-shore ?husband ?wife ?state))
             (same-shore ?other-guy ?wife ?state)))
  =>

  ;; Delete this state
  (retract ?state))

The final move-generating rule looks for circular paths -- states that lead from an identical state earlier in the tree -- and deletes them. This rule uses the "search-depth" and "locations" slots of the state facts directly. The ":" syntax introduces a Boolean function call that constrains that value of a variable -- i.e., "?sd2&:(< ?sd1 ?sd2)" means to assign the value of this slot to the variable ?sd2, but only if it's greater than ?sd1.

(defrule CONSTRAINTS::circular-path
  "If a path contains a duplicate state, it is cyclical,
  and should be discarded."

  (declare (auto-focus TRUE))
  (state (search-depth ?sd1) (locations ?map1))
  ?state <- (state (search-depth ?sd2&:(< ?sd1 ?sd2))
                   (locations ?map2&:(?map1 equals ?map2)))
  =>
  (retract ?state))

Displaying solutions

That's it! The preceding rules will generate all the possible solutions to the problem. Note that these rules are much more general than they could be, so they can actually solve many related problems: for example, they would still work with a different number of couples, and they'd even work if the list included unmarried people. Although there may not always actually be a solution for every set of initial conditions, if a solution exists, these rules will find it.

All that's left is to recognize solutions and print them out. Because a solution is actually a list of states, we need a data structure to represent one. This template holds a pointer to the latest state in the solution, and a list of moves. Each move in the list is just the names of the people who moved at that step. The moves list will be updated as the solution rules walk through the list of states, which are chained together by their "parent" slots.

(deftemplate SOLUTION::moves
  "A holder for a list of moves (i.e., a solution.)"
  (slot last-state)
  (multislot moves-list))

The first solution rule recognizes that a solution exists using the utility function all-across, which returns true when all the people in that state are on the other side; it then creates a "moves" fact to represent this solution.

(defrule SOLUTION::recognize-solution
  "If, in a particular state, all
   the people are on shore-2, then that
   state is the last move in a solution."
  (declare (auto-focus TRUE))
  ?state <- (state (parent ?parent)
                   (locations ?map&:(all-across ?map))
                   (last-move ?move))
  =>
  ;; Remove the state
  (retract ?state)

  ;; Create a "moves" fact to describe this solution
  (assert (moves (last-state ?parent) (moves-list ?move))))

The next rule iteratively updates the "moves" fact by adding new moves (the modify function updates the values in the individual slots of a fact; it's similar to calling a setter method in Java)

(defrule SOLUTION::further-solution
  "Walk down the list of states representing a solution,
  and accumulate the moves."
  ;; If there's a state
  ?state <- (state (parent ?parent) (last-move ?move))

  ;; and a moves list that indicates this state is the next step
  ?mv <- (moves (last-state ?state) (moves-list $?rest))
  =>

  ;; Then modify the moves list to include this state.
  (modify ?mv (last-state ?parent) (moves-list ?move ?rest)))

The initial state's "last-move" slot contains no-move, and its parent slot is nil (the Jess equivalent of Java's null). This acts as a sentinel and terminates the search for moves.

To actually display the solution, we just need to walk the contents of moves-list in a particular moves fact and print each item, appropriately formatted. Note that the bind function is how you assign a value to a variable in Jess.

(defrule SOLUTION::print-solution
  "A 'moves' fact representing a solution starts with 'no-move'.
   When we see one, print the whole thing out as a solution."

  ?mv <- (moves (last-state no-parent) (moves-list no-move $?moves))
  =>

  (retract ?mv)
  (bind ?i 1)
  (bind ?shore "shore-2")

  (printout t crlf "Solution found: " crlf crlf)
  (foreach ?move ?moves
    (printout t ?move
              (if (> (?thing indexOf " ") -1) then
                " move to "
                else
                " moves to ")
              ?shore crlf)
    (bind ?shore (opposite-of ?shore))
    (bind ?i (+ 1 ?i))))

The windup

These are all the utility functions we used in writing our rules. Some of them provide an interesting overview of how Jess code can interact with Java objects. Many of them work directly with the HashMap stored in the locations slot of each state fact. For example, the first function iterates though the map and returns true if all the people are located on the opposite shore. You can see the while loop is using a Java Iterator in the normal fashion.

(deffunction all-across (?map)
  "If none of the people are on shore-1, we've found a solution."
  (bind ?it ((?map values) iterator))
  (while (?it hasNext)
    (if (eq "shore-1" (?it next)) then
      (return FALSE)))
  (return TRUE))

Here are a few more simple functions. This one uses the compareTo method in the String class:

(deffunction alphabetical-order(?n1 ?n2)
  "Returns true if the two arguments are in alphabetical order."
  (> (?n1 compareTo ?n2) 0))

This one checks that the two given facts have the same "class name," indicating that the two people are of the same gender:

(deffunction same-gender(?p1 ?p2)
  (eq (?p1 getName) (?p2 getName)))

These Boolean functions check the contents of the HashMap in a given state to determine whether two people are on the same shore, or whether one person is on the same shore as the boat.

(deffunction same-shore-as-boat(?name ?state)
  (bind ?map (fact-slot-value ?state locations))
  (bind ?num (fact-slot-value ?state search-depth))
  (eq (?map get ?name) (boat-location ?num)))

(deffunction same-shore(?name1 ?name2 ?state)
  (bind ?map (fact-slot-value ?state locations))
  (eq (?map get ?name1) (?map get ?name2)))

These two functions actually create states. In both functions, the named people are moved to the other side of the river in the new state. Both use the Java clone method to make a copy of the previous state's HashMap and then change the appropriate entries.

(deffunction move-alone (?name ?state)
  ;; Get a copy of the locations map for the old state
  (bind ?map ((fact-slot-value ?state locations) clone))

  ;; Get the old search depth
  (bind ?num (fact-slot-value ?state search-depth))

  ;; Get the name of the new shore
  (bind ?newshore (opposite-of (?map get ?name)))

  ;; Update the map for the person's new location
  (?map put ?name ?newshore)

  ;; Create the new state fact
  (assert (state (search-depth (+ 1 ?num))
                 (parent ?state)
                 (locations ?map)
                 (last-move ?name)))

(deffunction move-together (?name1 ?name2 ?state)
  (bind ?map ((fact-slot-value ?state locations) clone))
  (bind ?num (fact-slot-value ?state search-depth))
  (bind ?newshore (opposite-of (?map get ?name1)))
  (?map put ?name1 ?newshore)
  (?map put ?name2 ?newshore)
  (assert (state (search-depth (+ 1 ?num))
                 (parent ?state)
                 (locations ?map)
                 (last-move (str-cat ?name1 " and " ?name2))))

These last two functions provide nice labels for the two shores. The first one contains the nugget of information that shore-1 and shore-2 are opposite one another.

(deffunction opposite-of (?shore)
  (if (eq ?shore "shore-1") then
    "shore-2"
    else
    "shore-1"))

(deffunction boat-location (?num)
  "The boat alternates between the two shores."
  (if (evenp ?num) then
    "shore-2"
    else
    "shore-1"))

The pitch

We're almost ready to run our program. The only remaining thing that's necessary is to create the initial state fact. We could hard-code the information, but I'm going to adhere to the D.R.Y. (Don't Repeat Yourself) principle and create the initial state by querying Jess for the list of all person facts, then iterating over that list.

(import java.util.HashMap)

(defquery MAIN::all-people
  "List all the person facts, so that we can set up the initial state."
  (person))

(deffunction set-initial-state ()
  "Set up the first state fact, in which all the people are on one
   side of the river. All the other state facts will be created by
   cloning this one."

  (bind ?map (new HashMap))

  ;; Get the list of all the people
  (bind ?it (run-query MAIN::all-people))

  ;; Populate the map
  (while (?it hasNext)
    (bind ?name (fact-slot-value ((?it next) fact 1) name))
    (?map put ?name shore-1))

  ;; Create the state
  (assert (state (search-depth 1)
                 (parent no-parent)
                 (locations ?map)
                 (last-move no-move))))

It's a home run

Now, we just execute the program:

;; Reset the engine, assert the deffacts
(reset)

;; Call the function that creates the initial state
(set-initial-state)

;; Finally, fire the rules!
(run)

If you've got the Jess library available in the file jess.jar, and this code in the file wives.txt, then you can run the program using the command

java -classpath jess.jar jess.Main wives.txt

The program finds 8 solutions to the problem as given, taking about one second to run. Each solution looks like

Solution found:

Cw and Bw move to shore-2
Cw moves to shore-1
Cw and Aw move to shore-2
Cw moves to shore-1
B and A move to shore-2
A and Aw move to shore-1
C and A move to shore-2
Bw moves to shore-1
Bw and Aw move to shore-2
Bw moves to shore-1
Cw and Bw move to shore-2

Conclusion

Rule-based programming is generally used in more serious pursuits than solving logic puzzles: in processing insurance applications, giving financial advice, making purchase recommendations, inventory control, implementing business rules in the enterprise, and more. Neverthess, the unique characteristics of rule engines make them an ideal way to attack this kind of problem as well. Solving puzzles with Jess is a good way to learn about declarative and rule-based programming. You can read more about Jess at "http://herzberg.ca.sandia.gov/jess"(free trial version available to download) or check out the book Jess in Action.

Return to Top

The RowSet Interface

One of the problems with JDBC is the lack of support for using the rows returned from a database in a way that makes them accessible without maintaining a connection to the database. The RowSet interface was added to J2SE 1.4 to respond to this problem. The API for that version did not include any implementations of this interface although several sample implementations have been included as part of the early release program. J2SE 1.5 will include five standard implementations of the RowSet interface. In this article I would like to answer some questions about what RowSets are and how they might be used and take an advanced look at the upcoming implementations.

Q: What is a RowSet?

A: A RowSet is a disconnected, serializable version of a JDBC ResultSet.

Q: Could you explain that a little more clearly?

A: One of the problems with working with a ResultSet is that you can't pass it around from class to class across a network or across the Internet. A ResultSet maintains a connection to a database and because of that it can't be serialized. There are many situations where it would be a nice feature to be able to pass a ResultSet from one Java class to another across a network.

Suppose you had a client that invokes a server process to get some rows from a database. This might be an applet accessing a servlet or a JavaBean invoking a J2EE session bean. The server process would create a ResultSet and then it would have to read the data from the ResultSet and load it into some type of Collection object or array. Of course, you might want to include the metadata from the request (column names, display lengths, etc.) so you would need to figure out some way to pass that as well. However, no matter how you solved that problem it wouldn't be a standard solution.

The RowSet could be used in place of creating that Collection object and worrying about how to pass metadata. The RowSet extends the ResultSet interface so it has all the methods of ResultSet. The RowSet can be serialized because it doesn't have a connection to any database. When you run the execute method of the RowSet, all the data from the query is loaded into the RowSet and the connection is closed. The RowSet is a disconnected object in that it does not need to be connected to the database in order to provide data. Since it is disconnected it can be passed across a network.

Q: Will a RowSet have all the functionality of a ResultSet such as scrolling and updating?

A: Absolutely! In fact, you can take your RowSet, scroll through it, update it, store it in a file, load it back from the file at a later date, and use it to update the database.

Q: So why do I need ResultSet?

A: There is an obvious limitation at work here. The ResultSet does not contain all the data from your query. Since it has a connection to the database, when you run the next() method if the ResultSet needs more data it can go to the database and get it. The RowSet can't do that since it isn't connected to the database so it must load and hold all the data from your query as soon as you run the execute() method. If your query returns a lot or rows you could encounter very slow processing and out of memory errors. However, if the number of rows to be returned is a reasonable number then a RowSet can be used.

Q: Wait a minute. You said that the API would be supplying five standard implementations of the RowSet. Why are we getting standard implementations of RowSet when none of the other interfaces in the API have standard implementations?

A: The RowSet is different than other JDBC interfaces in that you can write a RowSet to be vendor neutral. A third party could write a RowSet implementation that could be used with any JDBC-compliant database. The standard implementation supplied by Sun uses a ResultSet to read the rows from a database and then stores those rows as Row objects in a Vector inside the RowSet. In fact, a RowSet implementation could be written to get its data from any source. The only requirement is that the RowSet acts as if it was a ResultSet. Of course, there is no reason that a vendor couldn't write a RowSet implementation that is vendor specific.

Q: So what are these five standard implementations?

A: The standard implementations have been designed to provide a fairly good range of functionality. The implementations provided are:

CachedRowSetImpl - This is the implementation of the RowSet that is closest to the definition of RowSet functionality that we discussed earlier. There are two ways to load this RowSet. The execute( ) method will load the RowSet using a Connection object. The populate( ) method will load the RowSet from a previously loaded ResultSet.

WebRowSetImpl - This is very similar to the CachedRowSetImpl (it is a child class) but it also includes methods for converting the rows into an XML document and loading the RowSet with an XML document. The XML document can come from any Stream or Reader/Writer object. This could be especially useful for Web Services.

JdbcRowSetImpl - This is a different style of implementation that is probably less useful in normal circumstances. The purpose of this RowSet is to make a ResultSet look like a JavaBean. It is not serializable and it must maintain a connection to the database.

The remaining two implementations are used with the first three implementations:

FilteredRowSetImpl - This is used to filter data from an existing RowSet. The filter will skip records that don't match the criteria specified in the filter when a next() is used on the RowSet.

JoinRowSetImpl - This is used to simulate a SQL join command between two or more RowSet objects.

Q: Where can I find these standard implementations?

A: As of October 2003, these are available as "Public Review Draft" versions and can be downloaded from here: http://java.sun.com/products/jdbc/download.html

Return to Top

The Coffee House

A Pattern of Behavior

Return to Top

An Introduction to Java Development with NetBeans IDE
A NetBeans IDE Project Basics Tutorial

by Dirk Schreckmann

In a nutshell, what is the NetBeans IDE?

NetBeans IDE is a free, open source, popular (with approximately 1 million downloads), integrated development environment used by many developers. Out of the box, it provides built-in support for developing in Java, C, C++, XML, and HTML. And this author especially likes the support for editing JSPs, including syntax highlighting, HTML tag completion, JSP tag completion, and Java code completion.

NetBeans IDE is available for free downloaded at http://www.netbeans.org

Following are step-by-step instructions to help NetBeans IDE greenhorns to get started developing Java applications with NetBeans IDE. The basic steps described are as follows.

1. Create a new project
2. Mount a directory - specify a location to save project files
3. Add a new class to the project
4. Compile and run a Java program

1. Create a New Project

Start NetBeans.

Start a new project: Main Menu -> Project -> Project Manager -> New Project

Click New.

Give the project a name. Click OK.

2. Mount a directory - specify a location to save project files

To specify a location on a disk drive where project files will be stored, mount a directory as part of the project.

To the project, add a directory to hold project files: Main Menu -> File -> Mount Filesystem...

Under Filesystems, Select Local Directory. Click Next.

Select a directory to hold the project. (Note: Don't open the desired directory, just select it. If you accidentally open the desired directory, just click the up directory arrow next to the "Look in" drop down list, and then select the desired project directory with a single click.) Click Finish.

3. Add a new class to the project

Right mouse click on a mounted project directory. Select New -> Java Class

Name the class and click Finish.

Edit the Java class as desired. Following is the code used in this tutorial.

public class Foo
{
    public static void main(String[] args)
    {
        System.out.println("Hello World!");
    }
}

4. Compile and run a Java program

In the Filesystems Explorer, assure that the main Java class is selected.

Go to Main Menu -> Build -> Execute to compile and run the main Java class in one step.

Note: To just compile a class, go to Main Menu -> Build -> Compile.

After executing, you should see results similar to the following. (Note that the NetBeans IDE captures console output, not unlike JBuilder. So, the output of this program appears in the lower IDE panel.)

Resources

Again, NetBeans IDE is available for free download at www.netbeans.org

For further information and assistence on using NetBeans IDE, visit The NetBeans Community and don't forget to mosey on over to The IDEs and Other Tools Forum in the JavaRanch Saloon.

Return to Top

Installing a native library to the Applet client's computer

by Erika Kupkova

To use an external package including native libraries by an applet isn't that easy. It's not enough just to pack it to the applet's jar file - the run time machine would not find it.

You need to copy the native library to the client's JVM.

The InstallApplet does the installation of a java package to the client's JVM (both the native and java libraries). After the installation, the package becomes part of the JVM, so any applet can use it.

To have the right to write to the client's disk, the InstallApplet jar file has to be signed or the client's java security policy has to be modified.

In this particular case, the applet is signed and is installing the javatwain.dll and javatwain.jar libraries from the www.gnome.sk site. You can see this applet working online at http://www.gnome.sk/Twain/remote/www/twain/server/php/remote.html. As well as the applets using the "Morena 6.0 - Image Acquisition Framework for Java(tm) Platform" for remote scanning. Both javatwain.dll and javatwain.jar libraries are part of the Morena Package.

The code of the installation applet is below.

Return to Top

SSH Tunneling for Java RMI, Part-I

Abstract

This article is the first in a series of two, describing the steps to setup SSH tunneling for Java RMI. In this part, we focus on setting up SSH tunnel for interactions between (a) a RMI client and the RMI registry for looking up the remote reference; and (b) a RMI client and a RMI server for method invocations. The second part in the series will identify and address additional issues related to (a) SSH tunneling due to ability of an RMI programs to download code; and (b) presence of corporate firewalls between a RMI client and a RMI server.

Introduction

Much like most of the early networking technologies, Java RMI was designed for a trusted distributed computing environment (with the exception of security from downloaded code, I should add). In Java RMI, there is no authentication of communicating end-points, meaning the server program does not refuse service to unknown client programs and vice-versa. There is no privacy or confidentiality of the data being exchanged, meaning anyone connected to the network and with access to the proper tools can see and analyze invocation parameters and return values. Additionally, there is no guarantee of message integrity, meaning an intermediate node or program can modify the messages being exchanged and the end-points won't suspect a thing.

These security issues do not pose serious problems within the safety of a protected network, but could be serious security threats within a large corporate intranet or over the open Internet.

A common approach to make RMI secure is to use RMI over SSL. SSL, as we know, is a layer over TCP/IP and supports end-point authentication, message integrity and confidentiality. Though RMI does not use SSL by default, it is fairly straight-forward to add this support using custom socket factories as explained in this example from RMI documentation and illustrated in my J2EE Security for Servlets, EJBs and Web Services book.

However, use of RMI over SSL is not a panacea for all RMI security problems:

• RMI over SSL using custom socket factories does not protect the communication between the client program and the RMI registry.
• An organization may have standardized upon a different security solution, such as one based on SSH, and may not want to deal with the additional complexity of managing X.509 certificates for SSL.

In this article, we will describe how RMI applications can be secured within a network that relies on SSH for security needs. SSH is a security protocol that can be used for end point authentication, message integrity and confidentiality. It is already widely deployed and is used by developers for a variety of purposes such as command execution on a remote machine, remote login, file copy to remote machines and tunneling for a large number of third-party applications. A typical SSH implementation consists of a daemon program called sshd and clients ssh and scp.

The Setup

To understand and carry out the steps in setting up SSH tunneling, we will need two machines: one to run the client program and another to run the RMI Registry and server program. Both machines should have J2SE SDK. The client machine should have SSH client and the server machine should have SSH daemon. For testing purposes, it would be good if we are able to close all ports other than the port 22, where SSH daemon listens for incoming connections, on the server machine.

I used a Windows 2000 machine with J2SE SDK v1.4.2 and CygWin with OpenSSH (an open source implementation of SSH) as the client machine. For the server, I used a machine running RedHat Linux 8 and loaded with J2SE SDK v.1.4.2. Also, we will assume that an SSH daemon is running on the server machine (this is the case with normal Linux installation). This setup is shown in Figure 1.

RH Linux 8 is based on 2.4 kernel and allows control of open ports via iptables, a network packet filtering software for Linux. We will use it to shut off all ports but port 22 of the server machine in some of our experimentation.

SSH Tunneling

SSH tunneling between the client and the server machines allows a client program to communicate with the server program without directly establishing a TCP/IP connection with the server program, as shown in Figure 2.

The process of establishing the tunnel essentially involves starting the SSH client program on the client machine with information about the local ports to be forwarded, corresponding remote ports and the remote host running the SSH daemon. The SSH client, after going through the end point authentication, informs the SSH daemon about remote connection addresses and starts listening for incoming connections on all the local ports.

Whenever this SSH client gets a connection request on port that has been forwarded for tunneling, it accepts the connection and informs the SSH daemon, which, in turn, establishes connection with the corresponding remote address. After that, all data exchange between the client and the server program flows through the SSH client and the SSH daemon and is encrypted to ensure privacy and message integrity.

Enough theory! Let us now establish a SSH tunnel between the client and the server machine for a specific port. For this purpose, we will use the default HTTP port, port 80. Let us assume that the server machine has Apache HTTP daemon running on this port. You can verify this by pointing your browser to the server machine. Now we will block all ports other than the SSH port 22 by running the following commands, while logged-in to the server machine as root:

    [root@vishnu /]# /etc/init.d/iptables stop
    [root@vishnu /]# iptables -A INPUT -p tcp --syn --destination-port 22 -j ACCEPT
    [root@vishnu /]# iptables -A INPUT -p tcp -i lo --syn -j ACCEPT
    [root@vishnu /]# iptables -A INPUT -p tcp --syn -j DROP
    

The first command clears all the current entries for processing network traffic. These entries are created during system boot time by /etc/init.d/iptables script file based on rules in the file /etc/sysconfig/iptables. To re-instate these entries, simply issue the command:

    [root@vishnu /]# /etc/init.d/iptables start
    

Rest of the commands essentially define the rules for processing incoming SYN packets (SYN packets initiate a TCP/IP connection), and hence rules for accepting incoming TCP/IP connections. The first command sets up the rule to accept SYN packets destined to port 22. The second command accepts all SYN packets on the loopback interface. This is required for the SSH daemon to establish connection with other programs on the same machine. The last rule drops all other SYN packets.

After all ports, except port 22, have been blocked, point your browser to the server machine. Are you able to fetch the HTML page? If yes, you are not successful in blocking the ports. If the browser times out, the ports are blocked.

Let us establish a SSH tunnel so that port 7550 of the client machine is forwarded to port 80 of the server machine. Why port 7550? Well, it could be any unused port on the client machine. For our illustrations, we simply chose this specific port.

     c:\>ssh -N -L7550:vishnu:80 -l pankaj vishnu
     pankaj@vishnu's password: ********
    

Notice that the client has been authenticated via a password. It is also possible to setup SSH for public and private key based authentication.

To test the correct functioning of the tunnel, point your browser to the URL http://localhost:7550. This should display the HTML page served by the HTTP daemon of the server machine. As you would guess, under the hood, the browser talks to the local SSH client, the SSH client encrypts the message and forwards it to the SSH daemon on the server machine, which forwards it to the port 80, after decryption.

Now that we understand SSH tunneling, let us write a simple RMI program and see how this tunneling can be used for RMI.

A Simple RMI Program

This program consists of a Server program and a Client program. Source code for these programs are assumed to be available within a directory tree rooted at ex1, as shown below:

    ex1/server/EchoServerIntf.java
              /EchoServerImpl.java
              /Main.java
       /client/Main.java
    

The Server Program

The Server programs consists of Java interface EchoServerIntf, implementation class EchoServerImpl and the main class Main. Their sources, along with brief descriptions, are presented below:

The interface EchoServerIntf has only one operation: String echo(String inp).

      package server;

      public interface EchoServerIntf extends java.rmi.Remote {
        public String echo(String args) throws java.rmi.RemoteException;
      }

The implementation class EchoServerImpl extends the RMI class java.rmi.server.UnicastRemoteObject and implements the interface EchoServerIntf.

      package server;
      public class EchoServerImpl extends java.rmi.server.UnicastRemoteObject
			implements EchoServerIntf {
        private static int counter = -1;
        public EchoServerImpl() throws java.rmi.RemoteException {
          super();
        }
      public String echo(String arg) throws java.rmi.RemoteException {
        counter++;
        System.out.println("[" + counter + "] EchoServerImpl::echo(" + arg + ")");
          return "[" + counter + "] EchoServer>> " + arg;
        }
      }

The Main class creates an instance of EchoServerImpl and binds it to an RMI URL. Note that this URL assumes that the RMI Registry is running on the same machine as the main program.

      // File: ex1\server\Main.java
      package server;
      public class Main {
        public static void main(String[] args) throws Exception {
          EchoServerImpl impl = new EchoServerImpl();
          System.out.println("impl = " + impl);

          String url = "rmi://localhost/EchoServer";
          java.rmi.Naming.rebind(url, impl);

          System.out.println("EchoServer bound to the rmiregistry.");
          return;
	    }
      }

To compile the .java files and generate the stub and skeleton corresponding to the EchoServerImpl class, issue the following commands (assuming the current directory to be ex1):

    c:>\rmi-ssh\ex1>javac -classpath . server\*.java
    c:>\rmi-ssh\ex1>rmic -classpath . server.EchoServerImpl
    

Leave the compiled .class files in the same directory as the corresponding source files.

The Client Program

The client program consists of a single class with main() method. Within this method, it takes the hostname of the machine running the RMI registry as commandline argument, forms an RMI URL, retrieves the remote reference of the server RMI class by looking up the registry and invokes the echo() method.

      package client;
      import server.EchoServerIntf;

      public class Main {
        public static void main(String[] args) throws Exception {
          String host = "localhost"; // host running the rmiregistry
          String arg = "Hello, Java";
          if (args.length > 0)
            host = args[0];
          String url = "rmi://" + host + "/EchoServer";
          System.out.println("RMI Service url: " + url);

          EchoServerIntf obj = (EchoServerIntf)java.rmi.Naming.lookup(url);
          System.out.println("RMI Service stub: " + obj);
          System.out.println();
          System.out.println();

          System.out.println("Calling: stub.echo(" + arg + ")...");
          String ret = obj.echo(arg);
          System.out.println("... returned value: " + ret);
        }
      }

Compile this .java file:

    c:\rmi-ssh\ex1>javac -classpath . client\Main.java
    

Running the Programs

To see the RMI in action, We will run the RMI registry and the Server program on the Linux Box. To do this, transfer the complete directory structure to the Linux box (assuming that the sources were compiled on the Windows 2000 machine). Also, make sure that the normal ports are not blocked.

Now, run the rmiregistry from directory ex1, in its own shell window:

    [pankaj@vishnu ex1]$ export CLASSPATH=.
    [pankaj@vishnu ex1]$ rmiregistry
    

It is worthwhile to mention that by default, rmiregistry accepts connections on port 1099. Also, it needs access to the stub classes, either locally or by downloading from another machine, for all the Remote References that get registered with it.

We have set the CLASSPATH to the current directory so that rmiregistry can find the stub classes in CLASSPATH. This way we are able to avoid the need to download the stub classes. Note that some versions of JDK do not require explicit setting of CLASSPATH but some do.

The next step is to launch the main server program from a different shell window:

    [pankaj@vishnu ex1]$ java -cp . server.Main
    impl = server.EchoServerImpl[RemoteStub [ref: \
    [endpoint:[192.168.1.105:33045](local),objID:[0]]]]
    EchoServer bound to the rmiregistry.
    

Pay attention to the displayed value of the impl variable, of type EchoServerImpl. It indicates the IP address of the machine and a randomly assigned port. The client program uses this address and port combination to communicate with the server and hence has special significance for SSH tunneling.

Now that the server components are up and running, run the client program from the Windows 2000 machine, specifying the name of the server machine as a commandline argument.

    C:\rmi-ssh\ex1>java -cp . client.Main vishnu
    RMI Service url: rmi://vishnu/EchoServer
    RMI Service stub: server.EchoServerImpl_Stub[RemoteStub [ref: \
    [endpoint:[192.168.1.105:33045](remote),objID:[1ad086a:f7fad5260a:-8000, 0]]]]

    Calling: stub.echo(Hello, Java)...
    ... returned value: [0] EchoServer>> Hello, Java
    

You can see that the client displays the same endpoint address as the server.

Now use the iptables command, as explained in the SSH Tunneling section, to block all ports but port 22. After this, try running the client program. Does it succeed?

RMI Through SSH Tunnel

To create SSH tunnel for RMI calls, we need to forward two ports:

1. Port 1099 where rmiregistry waits for incoming connection. Doing this is fairly straight-forward.
2. The port at which the RMI server program waits for incoming connection. This requires some work, for, we have seen that the server program is assigned a random port. Another problem is that the remote reference obtained by the client program has the IP address of the server program. But for tunneling to work, the client needs to specify the localhost. As we will see soon, this is much harder to accomplish.

We can assign a fixed port to the RMI server program by adding an extra constructor to the EchoServerImpl and slightly modifying the main class. The modified sources can be found under directory ex2. The additional or modified code is shown below:

      package server;
      ...
      public EchoServerImpl(int port) throws java.rmi.RemoteException {
        super(port);
      }
      public EchoServerImpl(int port, java.rmi.server.RMIClientSocketFactory csf,
          java.rmi.server.RMIServerSocketFactory ssf) throws java.rmi.RemoteException {
        super(port, csf, ssf);
      }
      ...
      }

The first constructor allows a programmer assigned port to be used by the RMI server class for accepting connections. The second class allows not only specification of the port but also the mechanism to create the client and server sockets. As it is possible to create a ServerSocket tied with a specific address using the constructor ServerSocket(int port, int backlog, InetAddress bindAddr), one may think that it would be possible to specify special IP address "127.0.0.1", representing the loopback address, as the IP address for the RMI server class. However, this didn't work for me.

For SSH tunneling to work, we need the loopback address in the remote reference for the client program to connect to the SSH client on local machine. I was able to do this by modifying the DNS entry for the server machine so that resolving the hostname vishnu always returned the address "127.0.0.1" on machine vishnu. This is a hack which works but is not very elegant.

Now let us look at the modified main class that makes use of fixed port 9000 to construct the remote object.

    package server;

    public class Main {
      public static void main(String[] args) throws Exception {
        int inport = 9000;
        EchoServerImpl impl = new EchoServerImpl(inport);
        System.out.println("impl = " + impl);
        String url = "rmi://localhost/EchoServer";
        java.rmi.Naming.rebind(url, impl);
        System.out.println("EchoServer bound at port " + inport + " in rmiregistry.");
        return;
      }
    }

The compilation steps are same as in the last section and hence are not duplicated here.

To setup the tunnel for ports 1099 (for RMI registry) and 9000 (for RMI server), issue the following command on the client machine:

     c:\>ssh -N -v -L1099:vishnu:1099 -L9000:vishnu:9000 -l pankaj vishnu
     pankaj@vishnu's password: ********
    

Option -v directs the SSH client to print debug messages and helps in understanding exchange of messages.

Start the RMI registry and the server programs the same way as in the last section. While starting the client program, specify localhost as the commandline argument.

    C:\rmi-ssh\ex2>java -cp . client.Main localhost
    RMI Service url: rmi://localhost/EchoServer
    RMI Service stub: server.EchoServerImpl_Stub[RemoteStub [ref: \
    [endpoint:[127.0.0.1:9000](remote),objID:[1ad086a:f7fad5260a:-8000, 0]]]]

    Calling: stub.echo(Hello, Java)...
    ... returned value: [0] EchoServer>> Hello, Java
    

Congratulations! You got SSH tunneling for RMI working.

Next Part

The next part of this series will talk about setup requirements for code downloadable by RMI registry and the RMI client and the issues that arise due to SSH tunneling. We will also talk about how to tunnel the SSH tunnel itself through HTTP so that an RMI client sitting inside a corporate intranet can talk to an outside server.

Acknowledgment

The basic motivation for this article came from this discussion thread at JavaRanch Security forum.

References

1. Source files in a single ZIP file
2. J2EE Security for Servlets, EJBs and Web Services
3. Remote Computing via Ssh Port Tunneling
4. Iptables Basics

Return to Top

Mosey on in and pull up a stool. The JavaRanch Big Moose Saloon is the place to get your Java questions answered. Our bartenders keep the peace, and folks are pretty friendly anyways, so don't be shy!

Question: How to code review for performance?

Answer:Well folks, the conversation following this topic opener is a bit much to be pasting in this lil' rag. Head on over to The Performance Forum, and get yourself an earful of the good advice in Vikram Chandna's "How to code review for performance?" thread.

Return to Top

Scheduled Book Promotions for October and early November:

Starting Date	Book	Author(s)	Publisher	JavaRanch Forum
October 14	Beginning Java Objects: From Concepts to Code	Jacquie Barker	APress	Java in General (beginner)
October 21	Java Rules	Douglas Dunn	Addison Wesley	Programmer Certification (SCJP)
October 28	Head First EJB	Kathy Sierra and Bert Bates	O'Reilly	EJB Certification (SCBCD)
November 4	JUnit in Action	Vincent Massol	Manning	Testing

Return to Top