## Thursday, December 24, 2009

### Einstein's problem

Recently on the Haskell beginner's list, Patrick LeBoutillier posted a link to Einstein's problem, a logic puzzle attributed to Albert Einstein. Patrick requested comments on his solution, but because I had nothing better to do today other than watching the Star Wars films on Spike, I decided to come up with my own solution. (I did eventually look at his solution and at the excellent comments by Daniel Fischer, and the code I am presenting here includes changes based on those comments.)

According to the linked article, the puzzle is based on the following facts:

1. There are 5 houses (along the street) in 5 different colors: blue, green, red, white and yellow.

2. In each house lives a person of a different nationality: Brit, Dane, German, Norwegian and Swede.

3. These 5 owners

1. drink a certain beverage: beer, coffee, milk, tea and water,
2. smoke a certain brand of cigar: Blue Master, Dunhill, Pall Mall, Prince and blend, and
3. keep a certain pet: cat, bird, dog, fish and horse.

4. No owners have the same pet, smoke the same brand of cigar, or drink the same beverage.

It also include the following hints:

1. The Brit lives in a red house.

2. The Swede keeps dogs as pets.

3. The Dane drinks tea.

4. The green house is on the left of the white house (next to it).

5. The green house owner drinks coffee.

6. The person who smokes Pall Mall rears birds.

7. The owner of the yellow house smokes Dunhill.

8. The man living in the house right in the center drinks milk.

9. The Norwegian lives in the first house.

10. The man who smokes blend lives next to the one who keeps cats.

11. The man who keeps horses lives next to the man who smokes Dunhill.

12. The owner who smokes Blue Master drinks beer.

13. The German smokes Prince.

14. The Norwegian lives next to the blue house.

15. The man who smokes blend has a neighbor who drinks water.

The question is: Who keeps fish?

My solution follows:
import Data.Listimport Data.Maybedata House = Blue | Green | Red | White | Yellow deriving (Eq, Show, Enum, Bounded)data Nationality = Brit | Dane | German | Norwegian | Swede deriving (Eq, Show, Enum, Bounded)data Beverage = Beer | Coffee | Milk | Tea | Water deriving (Eq, Show, Enum, Bounded)data Cigar = BlueMaster | Dunhill | PallMall | Prince | Blend deriving (Eq, Show, Enum, Bounded)data Pet = Cat | Bird | Dog | Fish | Horse deriving (Eq, Show, Enum, Bounded)type Owner = (House, Nationality, Beverage, Cigar, Pet)

First, some preliminaries. I defined five types, each containing five values for each of the characteristics of the owners of the houses. Haskell is capable of automatically deriving instances of the typeclasses Eq, Show, Enum, and Bounded, automatically allowing the values of my types to be compared for equality, printed, and to act as enumerations (and bounded enumerations, which I will mention shortly). I also create a type to represent the characteristics of a given house.

My plan for finding the solution is significantly different from Patrick's; I decided naively to create a list of all possible combinations of the characteristics, filter out those that did not match the necessary hints, then create five-element permutations of the houses representing possible streets, and finally filter those streets to find the one satisfactory configuration. My goal was to make the simplest, clearest possible solution rather than the fastest.

Specifically, I did not want to encode any hint-specific details as structural elements of my code. What I wanted to do was to isolate things like "The Norwegian lives in the first house" to well-defined elements of the code rather than have them encoded as part of the system that generates the sequence of houses on the street.

To create the list of every possible Owner, I first needed lists of the possible values of each characteristic.
allValues :: (Enum a, Bounded a) => [a]allValues = [ minBound .. maxBound ]houses = allValuesnationalities = allValuesbeverages = allValuescigars = allValuespets = allValues

This is where the Bounded typeclass comes in. allValues is a polymorphic list of all of the elements of a bounded enumeration; its actual value depends on the type that it has when it is evaluated. Since it is polymorphic (and the type declaration for it is necessary), I can use it multiple times with different types. As a result, the houses list is typed as [House], the nationalities list is typed as [Nationality], and the others likewise; each takes the list of values for the appropriate type. (I did not bother to provide type declarations for each because that would be a lot of work, and the types are fixed by the next value. Type inference is wonderful.)
possibilities :: [Owner]possibilities = [ (house, nationality, beverage, cigar, pet)   | house <- houses,     nationality <- nationalities,     beverage <- beverages,     cigar <- cigars,     pet <- pets ]

The value of possibilities is a list of all possible combinations of each of the characteristics. It is defined by a list comprehension. house takes one value from houses, nationality from nationalities, and so on, and the result is the five-tuple creating an Owner. In fact, house takes on each value from houses in turn. As a result, possibilities has 3125 elements.

The next question is how to filter the possibilities. Several of the hints (1, 2, and 3 for example) relate to properties of a single household (or Owner). Take a look at hint 2 for instance. It says that the Swede's household contains the Dog; or alternatively, if a household contains the Swede then it contains the Dog and if a household contains the Dog, then it contains the Swede. If the household does not contain either the Swede or the Dog, then this hint provides no information. When filtering the possibilities, this hint disallows those households containing the Swede or the Dog, but not both. That is a standard logical connective, pronounced "if and only if", and written "iff" or "<->" (normal implication would be only half of <->, so it would be written "->"). So, what I need are base-level predicates indicating "this house has the Swede" and combinators like <->. This is how I did that:
type Predicate = Owner -> Boolhouse color (c,_,_,_,_) = color == cnationality nat (_,n,_,_,_) = nat == nbeverage bev (_,_,b,_,_) = bev == bcigar cig (_,_,_,c,_) = cig == cpet pt (_,_,_,_,p) = pt == p(<->) :: Predicate -> Predicate -> Predicate(<->) l r owner = ((not lo) || ro) && ((not ro) || lo)    where      lo = l owner      ro = r owner

A Predicate is a function which maps the five elements of an Owner (or household) to True, if the Owner matches the specific predicate, or False, if it does not. The following functions are used to define the base-level predicates: cigar accepts an argument, cig, which is one of the values of Cigar, and produces a Predicate (by virtue of Haskell's automatic currying). So, for example, "cigar Dunhill" results in a function which further takes an Owner and returns true if that Owner smokes Dunhill.

The <-> function takes two other predicates and uses them to compute a combined Predicate as in hint 6: (cigar PallMall) <-> (pet Bird), which indicates that any Owner which includes PallMall as a cigar should also include a Bird as a pet. <-> is defined using the two individual implications, adjusted by a standard transformation to use only negation and disjunction which are available in Haskell as standard operations. The only real complication of <-> is the additional Owner argument it takes and which it supplies to the lower-level Predicates.

How are these Predicates used? Here are the first group of hints:
hint1 = (house Red) <-> (nationality Brit)hint2 = (nationality Swede) <-> (pet Dog)hint3 = (nationality Dane) <-> (beverage Tea)hint5 = (house Green) <-> (beverage Coffee)hint6 = (cigar PallMall) <-> (pet Bird)hint7 = (house Yellow) <-> (cigar Dunhill)hintC = (beverage Beer) <-> (cigar BlueMaster)hintD = (nationality German) <-> (cigar Prince)

(I broke into hexadecimal for hints greater than 9 so everything would line up.)

To make use of the hints to filter the possibilities, I created another Predicate that allows me to conjoin the hint predicates into a single test to be applied to the possibilities. (Actually, I created two; I'll use the second, disjunction, later.) These are basically the normal logical and (&&) and or (||) lifted to work as Predicates instead of simple boolean operations.
(/\),(\/) :: Predicate -> Predicate -> Predicate(/\) l r o = (l o) && (r o)(\/) l r o = (l o) || (r o)possibilities' = filter (hint1 /\ hint2 /\ hint3 /\ hint5 /\ hint6 /\ hint7 /\ hintC /\ hintD) possibilities

If you are curious, /\ is "and" and \/ is "or" in the first logical notation I learned.)

These hints filter possibilities significantly; possibilities has 3125 elements and possibilities' has only 78. However, the remaining hints relate Owners together with their positions on a Street, which is another kettle of fish.
type Street = [Owner]

Since I know there are five houses on the street, a Street will be a five-element list. I could have used a better representation for this, one that would explicitly show the number of households, but I figured that would be an unnecessary complication that would better be left implicit.

For the moment, I intend to ignore how I get the Streets. Instead, I first focused on further, higher-level predicates that operate on Streets. To make these predicates simpler, I chose to represent a StreetPredicate as a function from a Street to a "Maybe Street"; this is a standard Haskell type containing either Just a Street, or Nothing. The first case indicates that the Street satisfies the predicate (which returns the Street instead of True) and the second case indicates the Street does not satisfy the predicate (which returns a special value Nothing).
type StreetPredicate = Street -> Maybe Street

My first StreetPredicate is from hint 4, which indicates that one household is immediately left of another.
leftOf :: Predicate -> Predicate -> StreetPredicateleftOf o1 o2 st = do i <- (findIndex o1 st)                     h <- if i < 4 then Just $st !! (i+1) else Nothing if o2 h then Just st else Nothing Per the type declaration, this function takes two house-based Predicates and produces a StreetPredicate; it does so by finding the first Owner on the Street who satisfies the first Predicate, checks that it is possible to have a house to its right, and then checks that the Owner to the right satisfies the second Predicate. This function takes the form of a Haskell monadic operation, specifically the Maybe monad, which takes three steps in this function. If either of the first two returns Nothing, the overall function returns Nothing without evaluating the remainder. Assuming execution gets to the final if step, it directly produces either Just the Street st, or Nothing. (Behold the wonder of monads in Haskell!) Another similar StreetPredicate checks whether two Owners on a Street identified by Predicates are next-door neighbors. nextTo :: Predicate -> Predicate -> StreetPredicatenextTo o p st = do i <- (findIndex o st) j <- (findIndex p st) if abs (i-j) == 1 then Just st else Nothing Finally, I created a couple of StreetPredicates to definitively locate households by address. In this case, 0 is the address of the first house on the Street and 2 is the center house on the Street. address :: Int -> Predicate -> StreetPredicateaddress i p st = if p$ st !! i then Just st else Nothingcenter = address 2first = address 0

The remaining hints can be written as:
hint4 = (house Green) leftOf (house White)hint8 = center $beverage Milkhint9 = first$ nationality NorwegianhintA = (cigar Blend) nextTo (pet Cat)hintB = (pet Horse) nextTo (cigar Dunhill)hintE = (nationality Norwegian) nextTo (house Blue)hintF = (cigar Blend) nextTo (beverage Water)

As above, I need a way to combine the individual hint StreetPredicates. That is the job of the /^\ operator, which is roughly equivalent to conjunction. (Think of it as a larger version of /\ with the top smushed down.)
(/^\) :: StreetPredicate -> StreetPredicate -> StreetPredicate(/^\) l r s = do { ls <- l s; rs <- r s; return s }

This function is defined using the Maybe monad; it returns Just the Street s as long as both the two prior steps do not return Nothing.

Now I have gotten to the hairy part. I have a list of 78 possibly satisfactory households, and I wish to filter all possible permutations of five of those households to find the one Street which meets all of the requirements. Creating permutations is relatively simple in Haskell, but as it turns out there are over 2 million such permutations. That is far too many to handle. Continuing my tradition of being only as smart as necessary, I have to get a little smarter when creating my Street permutations (but only a little).
outOf :: Int -> [Owner] -> [Street]outOf 0 _ = [[]]outOf n xs = [ x:xs' | x <- xs, xs' <- (n-1) outOf (delete x xs) ]    where      delete (h,n,b,c,p) = filter (not . (house h \/ nationality n \/ beverage b \/ cigar c \/ pet p))

Think of outOf as being used infix, as in "2 outOf [1,2,3]", which produces all possible two element permutations from the three element list.

Using the normal definition of delete, this function would produce all 2 million-plus five element permutations ("delete x xs" returns a list of the elements of the list xs that are not equal to x). My minimal smartness is to notice that this is a list of Owners, and that only one Owner on the street can drink Coffee, for example. So, instead of merely removing those elements equal to x, I remove all of them which match it in any characteristic, using the \/ operator I created earlier, the basic Predicates, and a logical negation. ("delete" would normally be something like "delete x xs = filter (\y -> not (x == y)) xs".) The length of "5 outOf possibilities'" is only 54720 elements, which is enough of an improvement. I would argue that this is the one place where I have some part of the details of the problem hidden in the structure of my code, but boy do I need this one.

The final results are:
results = mapMaybe (hint4 /^\ hint8 /^\ hint9 /^\ hintA /^\ hintB /^\ hintE /^\ hintF) \$ 5 outOf possibilities'

This uses mapMaybe, which is somewhat similar to filter except in using Maybes rather that Bools. results finally evaluates to a list containing a single Street, describing the single configuration which satisfies all of the hints.

Conclusions?

First I would like to note that hintF (number 15) is not necessary. The problem is actually over-determined; eliminating hint 15 still results in only one result. None of the other StreetPredicate hints can be removed; I did not check the Predicate hints.

Performance-wise, it is not actually horrible. Subsequent to the mailing list suggestions to Patrick's original solution, his code is somewhere between 5% (interpreted using runhaskell) and a third (compiled) faster than mine. Now, I do not make any claims that mine is particularly idiomatic Haskell, nor that it is in any way fast. However, it seems perfectly acceptable.

My last blog post was about Whitehead's comments on notation. Haskell in this instance has provided some incredible tools for notation. Specifically, I like the ability to define the hints clearly and independently and the ability to operate with multiple levels of logical predicates. In effect, what I have done with my <->, /\, \/, /^\, and so on, is to define a simplified domain-specific language for solving this specific problem.

I could think of implementing the same approach using Java, but the result would be much more verbose if possibly equally satisfactory. As I was discussing with a coworker recently, functional programming (closures in that instance, currying and combinators in this) do not necessarily provide features that cannot be lived without, but having them is much preferable to not having them.

I recently listened to a Software Engineering Radio podcast on the difference between Computer Science and Software Engineering. I will have more to write on that topic at some point soon, but I would like to point out that my solution to this problem (toy that it is) is pure Computer Science with a big C and big S. From Haskell, typeclasses, my idiotic filtering approach, to predicate calculus with custom domain specific predicates, nothing I have done in solving this problem has doodley squat to do with software engineering. Or, from the other side, nothing in my 100-ish lines of code would be apparent to a software engineer who was not interested in ivory-tower, high-falootin', theorem proving Computer Science. And that is bad. What I have done by deliberately avoiding encoding parts of the problem as structural elements in the code, by going out of my way to create as generic a domain specific language as I could, by using a collection of tools straight out of pure Computer Science, is better engineering than anything I would have come up with by going straight at the problem.

In fact, the major criticism I keep hearing in the back of my head about this code is that it is too advanced, too CS-y, too hard for a typical developer to support, understand, and maintain going forward. On the one hand, that criticism is something I understand, something I have to live with, since it is true. The typical developer I have worked with over the last 20-ish years is not going to want to deal with this kind of code. On the other hand, as a professional programmer myself, I find that criticism (and the daily situation) deeply offensive.

## Tuesday, December 22, 2009

### Alfred North Whitehead on notation

This really has little to do with anything, but I have been searching for the source of a quote on the power of good notation for a long time, and I believe I have finally found it. This is from Alfred North Whitehead's An introduction to mathematics:
By relieving the brain of all unnecessary work, a good notation sets it free to concentrate on more advanced problems, and in effect increases the mental power of the race.

He goes on with,
Probably nothing in the modern world would have more astonished a Greek mathematician than to learn that...the whole population of Western Europe...could perform the operation of division for the largest numbers....

It is a profoundly erroneous truism...that we should cultivate the habit of thinking what we are doing. The precise opposite is the case. Civilization advances by extending the number of important operations which we can perform without thinking about them. Operations of thought are like cavalry charges in a battle---they are strictly limited in number, they require fresh horses, and must only be made at decisive moments.

## Sunday, December 13, 2009

### SPNEGO authentication

I have written previously about authenticating against Active Directory using LDAP, and I will probably be writing in the future about authenticating using a username and password against AD's Kerberos, but I have not mentioned the original reason for my interest in the grinding toil of groveling through Microsoft authentication protocols.

The Simple and Protected GSSAPI Negotiation scheme and its application to HTTP provide a nice solution to single sign-on to web applications in a Kerberos-based authentication environment. It works basically like this:

1. The browser connects to the server and makes a request.

2. The server determines that the client is not authorized and the request has no authorization information in it, and denies the request with a 401 status code and a "WWW-Authenticate" header of "Negotiate".

3. The browser identifies that it has Kerberos authentication information available (a cached TGT, for example). It requests a ticket for the server from the ticket-grating authority and re-sends the original request with the ticket (wrapped in some GSS-API nonsense and base-64 encoded) in the "Authorization" header.

4. The server recovers the ticket and validates it, based on its pre-authentication with the same Kerberos authority. Assuming the ticket validates, the server replies successfully to the request, possibly adding some authentication-negotiation-related information to the response.

There are some complications; the negotiation may take more than one round, etc., but for the most-common, successful case, it is a straightforward, relatively lightweight protocol that does not require (nor allow, for that matter) any user effort. So, how do you do this for a Java web application? Well, I have a servlet filter that implements the authentication protocol, and I would like to describe it here.

A servlet filter implementation requires three methods, and destroy() is currently unused. That leaves init(FilterConfig) and doFilter(ServletRequest, ServletResponse, FilterChain). init() handles the configuration, based on the configuration in the web app's web.xml file.

The first part of init recovers four pieces of information from the configuration:

• The service's Service Principal Name (SPN).

• The location of the key tab file containing the SPN's private key.

• Whether or not some debugging info should be printed.

• A regular expression describing resources such as images or freely-accessible pages which should not require authentication.

    final String spn = filterConfig.getInitParameter(SERVICE_PRINCIPAL_NAME_PARAMETER);    final String keyTab = filterConfig.getInitParameter(SERVICE_KEYTAB_FILE_PARAMETER);    if (spn == null || keyTab == null)    {      throw new ServletException( String.format("both %s and %s must be set", SERVICE_PRINCIPAL_NAME_PARAMETER, SERVICE_KEYTAB_FILE_PARAMETER) );    }    String passExpression = filterConfig.getInitParameter(NON_AUTHENTICATED_REGEX_PATTERN);    if (passExpression != null)    {      try      {        passPattern = Pattern.compile(passExpression);      }      catch (PatternSyntaxException e)      {        throw new ServletException( String.format("invalid %s expression: %s", NON_AUTHENTICATED_REGEX_PATTERN, passExpression), e);      }    }    final String debugParameter = filterConfig.getInitParameter(DEBUG_PARAMETER);    final boolean debug = (debugParameter != null && debugParameter.equalsIgnoreCase("true"));

Given these four items (actually, just the first three), I can create a Java standard Subject object which can validate incoming tickets.
    final Configuration loginConfig = new KerberosLoginConfiguration(spn, keyTab, debug);    final Set principals = new HashSet(1);    principals.add(new KerberosPrincipal(spn));    final Subject subject = new Subject(false, principals, Collections.EMPTY_SET, Collections.EMPTY_SET);    try    {      final LoginContext loginContext = new LoginContext("", subject, null, loginConfig);      loginContext.login();      serviceSubject = loginContext.getSubject();    }    catch (LoginException e)    {      throw new ServletException( String.format("cannot login to %s with %s", spn, keyTab), e);    }

(This implementation is based on an example from Spring Security; my original implementation required several much uglier custom classes.)

The SPN, keytab file path, and debug flag are encoded in a KerberosLoginConfiguration which is used to conceptually pre-authenticate the server's resulting serviceSubject. The key is the keytab file, which contains the private key for the SPN, which is associated with a Kerberos account and exported from Active Directory. This keytab file should be should be protected in much the same way as an SSL key.

public class KerberosLoginConfiguration extends Configuration{  private final Map options = new HashMap();  public KerberosLoginConfiguration(String spn, String keyTabFile, boolean debug)  {    options.put("useKeyTab", "true");    options.put("storeKey", "true");    options.put("doNotPrompt", "true");    options.put("isInitiator", "false");    options.put("keyTab", keyTabFile);    options.put("principal", spn);    options.put("debug", Boolean.toString(debug));  }  @Override  public AppConfigurationEntry[] getAppConfigurationEntry(String name)  {    final AppConfigurationEntry[] entries = {        new AppConfigurationEntry(BaseKerberosSpnegoFilter.KERBEROS_LOGIN_MODULE, AppConfigurationEntry.LoginModuleControlFlag.REQUIRED, options)    };    return entries;  }}

(All of this is using the hideous JAAS interfaces. I'm sorry.)

The Configuration contains a number of elements needed to configure a com.sun.security.auth.module.Krb5LoginModule, the value of KERBEROS_LOGIN_MODULE, to use the SPN and keytab file, and ultimately to handle the SPNEGO negotiation.

Once I have the serviceSubject, which is an attribute of the Filter implementation, I am off to the races. The actual filter starts by managing some necessary trivia.

• First, it checks if the request is trying to sneak information in using one of the mechanisms that I use to pass authentication on to the application. Silly, yes, but, well, there you are.

• Then, it checks whether it should just pass the request on. See passRequest below.

• Finally, it picks out the Authorization header and parses the result. If the header does not exist, it returns the result which starts the negotiation.

    final HttpServletRequest request = (HttpServletRequest) req;    final HttpServletResponse response = (HttpServletResponse) resp;    if (request.getHeader(KerberosAuthenticatedHttpRequest.AUTHENTICATED_USER_HEADER) != null)    {      // Don't come back now, ya hear?      log.warn(String.format("%s header set in request", KerberosAuthenticatedHttpRequest.AUTHENTICATED_USER_HEADER));      response.sendError(HttpServletResponse.SC_BAD_REQUEST, String.format("%s header set in request", KerberosAuthenticatedHttpRequest.AUTHENTICATED_USER_HEADER));      return;    }    if (passRequest(request))    {      chain.doFilter(request, response);      return;    }    final String header = request.getHeader(AUTHORIZATION_HEADER);    if (header == null)    {      response.setHeader(WWW_AUTHENTICATE_HEADER, NEGOTIATE_HEADER_VALUE);      response.setStatus(HttpServletResponse.SC_UNAUTHORIZED);      return;    }    final String[] elements = header.split(" +");    if (! elements[0].equalsIgnoreCase("Negotiate"))    {      response.sendError(HttpServletResponse.SC_BAD_REQUEST, String.format("unknown authentication mechanism '%s'", header));      return;    }    else if (elements.length != 2 || elements[1] == null)    {      response.sendError(HttpServletResponse.SC_BAD_REQUEST, String.format("unable to get SPNEGO ticket in '%s'", header));      return;    }

Once the preliminaries are handled, the ticket validation can begin.
    try    {      final SpnegoTicketValidator validator = Subject.doAs(serviceSubject, new SpnegoTicketValidator(elements[1]));      if (validator.getNextToken() != null)      {        response.setHeader(WWW_AUTHENTICATE_HEADER, String.format("%s %s", NEGOTIATE_HEADER_VALUE, validator.getNextToken()));      }      final GSSContext context = validator.getContext();      if (! context.isEstablished())      {        response.setStatus(HttpServletResponse.SC_UNAUTHORIZED);        return;      }      // Authentication accepted; continue with request      chain.doFilter(new KerberosAuthenticatedHttpRequest(request, context), response);      // Dispose of the GSSContext, freeing any resources.      try      {        context.dispose();      }      catch (GSSException e)      {        System.err.println("error disposing of GSSContext");        e.printStackTrace(System.err);      }    }    catch (PrivilegedActionException e)    {      response.sendError(HttpServletResponse.SC_UNAUTHORIZED, "authorization failed");    }

Actually, the third line and the SpnegoTicketValidator object handles the important parts. The rest is more details. The ticket negotiation may have another token to pass back to the client, or the negotiation may not be complete; these two situations must be handled before the request is passed on to the client. Once the request is handled, the GSSContext should be free'ed. (And I just noticed a bug; the context should be disposed if the negotiation is not complete. Gotta fix that.)

The request is wrapped by a KerberosAuthenticatedHttpRequest, to pass the authentication information to the application. The important part is the SpnegoTicketValidator.
public class SpnegoTicketValidator implements PrivilegedExceptionAction{  final private byte[] token;  private GSSContext context;  private byte[] nextToken;  public SpnegoTicketValidator(String ticket)  {    this.token = Base64.decodeBase64(ticket.getBytes());  }  @Override  public SpnegoTicketValidator run() throws Exception  {    context = GSSManager.getInstance().createContext((GSSCredential) null);    nextToken = context.acceptSecContext(token, 0, token.length);    return this;  }  public GSSContext getContext()  {    return context;  }  public String getNextToken()  {    return (nextToken == null) ? null : new String( Base64.encodeBase64(nextToken) );  }}

The key is the cryptographic context; after it accepts the token, assuming the negotiation is complete, it contains the information about the user on the other end of the connection. This class also hangs onto the possible next token to return to the client.

There remains only a few loose ends. One is the passRequest method, which I wrote in this way to allow subclasses to override it with more complicated pass/authenticate decisions.
  protected boolean passRequest(HttpServletRequest request)  {    if (passPattern == null)    {      return false;    }    StringBuffer url = request.getRequestURL();    String queryString = request.getQueryString();    if (queryString != null)    {      url.append('?').append(queryString);    }    return passPattern.matcher(url).matches();  }

The other loose end in the KerberosAuthenticatedHttpRequest, which I am too tired to reproduce at the moment. The highlights are:

• context.getSrcName().toString() provides the user's identity in the form of "username@domain".

• new KerberosPrincipal( context.getSrcName().toString() ) creates an implementation of the Principal interface.