Internet DRAFT - draft-goenka-java-complex-search
draft-goenka-java-complex-search
INTERNET DRAFT Vishal Goenka
Novell, Inc.
Expires in six months from 5 January 1999
Intended Category: Standards Track
Complex Directory Lookup using
Java Based LDAP Query Extension
<draft-goenka-java-complex-search-00.txt>
1. Status of this memo
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its
areas, and its working groups. Note that other groups may also
distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-
Drafts as reference material or to cite them other than as
"work in progress."
To view the list Internet-Draft Shadow Directories, see
http://www.ietf.org/shadow.html.
2. Abstract
LDAP provides some simple primitives to construct search
filters. Complex LDAP search queries such as those involving
joins or functional evaluation of simple query results require
client side processing of the intermediate search results. The
network overhead of retrieving intermediate results can be
substantial for large databases. This document defines an LDAP
extension for supporting server side evaluation of complex
search queries.
Custom search logic can be sent across to the server,
encapsulated as a Java Object. The LDAP server supporting this
extension would instantiate the java object and invoke its well
known interfaces in a JVM. The java object running at the server
end acts as the client-proxy, and makes a local search query to
the LDAP server. The directory entries are evaluated using the
Goenka INTERNET DRAFT [Page 1]
<draft-ietf-ldapext-java-complex-search.txt> January 1998
custom logic embedded in the client-proxy, and those that
satisfy the evaluation function are returned as the search
result to the LDAP server, which passes it back to the
originating client. Even non-Java LDAP clients can use this
method, provided the search query is written as a java object.
3. Introduction
Directory is at the heart of many powerful and distributed
applications today. The protocol most widely used to access a
directory is LDAP, which is largely implemented in a procedural
language like C. With the widespread use of directory for
variety of applications, the lookup queries would no longer be
simple exact/partial matches of a subset of object attributes.
Complex search queries involving joins or functional evaluation
of simple query results would be quite common. An example of a
search involving joins is : "Get me all the names and phone
numbers of all printer administrators", which currently would
require one query to get the administrator attribute of all
printer objects and then separate queries to get the phone
number for each administrator. A query based on functional
evaluation would be one, where the search criteria is based on a
function, f(x) of a simple query result x, rather than on x
itself. An example is a X.509 Certificate parsing function,
which returns a particular attribute (say key usage) of a BER
encoded X.509 Certificate. Assuming that a user's public key
certificates are stored in the directory as simple attributes
(byte array) rather than as objects, a search for the Root CA
(Certification Authority) of a user's data encryption public key
certificate would require retrieving all the certificates of the
user, parsing them at the client side to find the one
corresponding to the data encryption public key, and issuing
another set of search queries to find each certificate's CA,
till the root CA is reached.
Search queries can be simple enough to be built from rather
simple primitives or could be quite complex to require special
logic for evaluation. Using LDAP, a client would resolve a
complex query by fetching many directory entries from the server
and evaluating each of them at the client side, issuing further
queries based on intermediate results till the final desired
result is found. Unless, the search space can be reduced at the
server end, using some exact/partial matches, this would be
prohibitively expensive for large directory databases.
This document outlines an efficient alternative for such
enhanced directory search operations.
3.1 Problem Description
Goenka INTERNET DRAFT [Page 2]
<draft-ietf-ldapext-java-complex-search.txt> January 1998
LDAP provides some simple primitives to construct search
filters. Specific implementations can provide custom matching
rules (called extensibleMatch), although they can't be updated
dynamically. It is not possible to communicate a complex search
filter (like join operation logic or X509 Certificate Parsing
logic to retrieve specific attributes of a BER encoded X509
Certificate) using the available mechanisms.
3.2 Proposal Overview
The key reason for the above problem is the inability to run a
piece of client code securely at the server end. Java, with its
write-once-run-anywhere feature, along with technologies for
secure object migration, namely, serialization, reflection,
security features etc., seems to address this glitch. With wider
acceptance of Java as the Internet programming language, it is
perceivable to have many directory based applications written in
Java, which would use LDAP to access existing directories. It
therefore, makes good business sense to enable at least Java
LDAP clients to take advantage of java code mobility for complex
directory lookups. Even non-Java LDAP clients can use this
method, provided the search query is written as a java object.
The key idea is to define an LDAP extension, for sending queries
encapsulated as Java Objects. The LDAP servers supporting this
extension would instantiate the java object and invoke its well
known interfaces (discussed later) in a JVM. The java object
running at the server end acts as the client-proxy, and makes a
local search query to the LDAP server. The directory entries are
evaluated using the custom logic embedded in the client-proxy,
and those that satisfy the evaluation function are returned as
the search result to the LDAP server, which passes it back to
the originating client.
3.3 Salient Features
There are a few salient features to be noted in the current
proposal. The client-proxy interacts with the LDAP server using
LDAP calls itself, as a result of which, there is no change
required in the implementation of the LDAP APIs at the server
end, except for inclusion of an extension handler. Also, the
server can associate the same set of permissions with the LDAP
connection started by the client-proxy, as is associated with
the ongoing LDAP connection with the client, thereby simplifying
the access restrictions. Secondly, only the client-proxy code
needs to be in java, not the client code, since the client-proxy
does not need to interact directly with the client. This has
important consequences, in that even LDAP clients written in
languages like C can take advantage of this model for complex
queries, by simply storing the serialized java objects and their
Goenka INTERNET DRAFT [Page 3]
<draft-ietf-ldapext-java-complex-search.txt> January 1998
class definitions for the requisite queries. Thirdly, Java LDAP
clients can reuse a large chunk of their existing code designed
to filter a search query, by sending it across to servers who
support the proposed extension, and executing it locally if the
extension is not supported (the default choice).
3.4 Goals and Requirements
The requirements of this specification are :
- to provide a simple way of indicating time-based resource
requirements for executing client code on the server side
- to provide a light-weight way of communicating the client
proxy code to the server, including all java objects and
required class definitions
- to provide a uniform and extendible interface and data format
for securely executing client proxycode on the server and
communicating the results back to the client
The goals of this document are :
- to show the way in which the notion of a client-proxy is used
to extend the capability of LDAP search operations
- to describe the data structure of the LDAP extended operation
for communicating java objects encapsulating search queries
- to indicate an appropriate design for implementing the
extension handler at the LDAP server, requiring minimum changes
to the server code
- to address the security concerns of executing client code at
server side
4. Security Considerations
There are two different aspects of security associated with the
above proposal. The first one concerns the security of data at
the server. With appropriate set of java permissions associated
with the client-proxy code (java object), its possible to ensure
the security of execution of the client code at the server end.
This aspect of security is analogous to the applet security
considerations.
The second aspect is the fairness of execution. Its possible for
the client-code (malicious, bug-ridden or otherwise) to take
more than its fair share of server processing time. The client
Goenka INTERNET DRAFT [Page 4]
<draft-ietf-ldapext-java-complex-search.txt> January 1998
could use the lease model [6] to negotiate an approximate
processing time at the server end. The server would use the
client authentication information, along with current load to
grant a lease for appropriate time. The java thread executing
the query (a method of the java object) on the server could be
killed if the lease expires, unless the lease is renewed. The
details of the leasing model are discussed in the following
section.
5. Lease of Server Resources
The lease model is used to negotiate the resource requirements
at the server-side. The server resources to be considered for
lease are execution time, memory usage, I/O resources (e.g.,
reading from or writing to files) and network resources such as
sockets.
- Execution Time -- The client indicates the estimated and
maximum values of execution time that might be required by the
client-proxy. The server should either completely deny the lease
or grant for atleast estimatedDuration up to a maximum of
maxDuration. If the leased duration is elapsed and the
client-proxy is still executing, the server can either extend
the lease (depending upon server load conditions) or terminate
the client-proxy thread.
- Memory Usage -- Unfortunately, there is no simple known way to
restrict the memory usage of a Java program. Conceptually, a
java thread can go on allocating new objects, till the JVM runs
out of memory. However, it is desirable to limit the memory
usage of the client-proxy to the amount granted by the server as
part of the lease, if possible to enforce. The memory grant
should be atleast equal to estimatedMemory, up to a maximum of
maxMemory. The server can choose to ignore this, if it is
difficult to implement.
- I/O and Network Resources -- It is not expected of the
client-proxy to use the I/O or network resources at the server
side. An LDAP socket would be provided to the client-proxy by
the bootstrap code at the server to communicate with the LDAP
server locally. Java Permissions (as defined by
RequestedPermissions) are to be used to restrict or selectively
allow usage of specific I/O or network resources.
The lease response contains the lease granted to the client.
Server implementations are free to implement their own
algorithms to decide the lease grant for time-duration and
memory usage depending upon the client's rights and server load
conditions.
Goenka INTERNET DRAFT [Page 5]
<draft-ietf-ldapext-java-complex-search.txt> January 1998
5.1 Lease Renewal
A client-proxy might need to execute for a much longer duration
to complete, though it might be able to generate partial results
in much shorter time. A server might be unable to grant lease
for the entire requested duration (maxDuration) at first
negotiation, but would be fine with renewing the grant for
another chunk of time, depending upon load conditions. If the
client- proxy hasn't finished executing completely till the
granted lease expires, the server can choose to renew the lease
up to a maximum of maxDuration minus the previous grant. Once a
granted lease expires, the server must notify the client about
either the lease renewal or the termination of the client-proxy.
(The lease grant on resources other than execution time would
have to be handled in an analogous way.)
6. Architecture for JVM activation and client-proxy execution
The current architecture assumes no change to the existing LDAP
server other than an extension handler for "Java based Search
Query Extension". The extension handler parses the extended
operation request, and determines whether the requirements to
invoke a JVM for client-proxy activation are met. The basic
requirements include :
- Lease Grant : Does the server have enough resources to grant
the requested lease for server resources?
- Java LDAP implementation : Does the server have an
implementation of LDAP in Java, conforming to the interface that
the client-proxy is written to? There are two possible standards
emerging, namely, JNDI (Java Naming and Directory Interface)
with LDAP binding, and java LDAP API [1]. It is expected that
the server may already have the class files corresponding to
such standards, in which case these classes need not be sent as
part of the query. For clients which are written to proprietary
java LDAP interfaces, the implementation for the same must be
supplied in a jar.
- Java Permissions : Does the server policy allow granting the
requested java permissions to the client-proxy code, possibly
based on the client's authentication credentials.
An appropriate response is sent to the client, whether or not
the requirements for activation are met. If the requirements are
met, the server launches a JVM (or communicates with an existing
JVM), and schedules the activation and execution of the
client-proxy. The activation thread in Java creates a class
loader, to read the required classes from the jar accompanying
the request. Appropriate permissions are associated with the
Goenka INTERNET DRAFT [Page 6]
<draft-ietf-ldapext-java-complex-search.txt> January 1998
protection domain defined by these classes. Next, an LDAP
connection is opened with the server, and the permissions of the
requesting client are associated with the connection, using the
internal APIs of the LDAP server. Finally, the java object
encapsulating the query is de-serialized, using the readObject()
method of the object's class. The LDAP connection is passed as
an argument to the startup function (say, run()) and the
activation thread starts executing the client-proxy. The
client-proxy code uses the given LDAP connection to make LDAP
search queries to the server. Separate methods are provided to
return partial results, and to query the progress of the
client-proxy.
A sample interface definition for the client-proxy is as
follows:
public interface LDAPClientProxy implements java.io.Serializable {
/**
* The startup function, which queries the LDAP server using the
* given LDAPConnection. The partial results are stored
* internally such that they can be retrieved at any time, using
* getPartialResults().
*/
void run (LDAPConnection ld);
/**
* Returns the partial results (if available). The results are
* formatted as a byte [], which is interpreted by the client.
* null is returned, if there are no partial results available.
*/
byte [] getPartialResults();
/**
* Returns the progress in terms of percentage (0-100). This
* helps the monitor thread to gauge the progress, and take the
* lease renewal decisions. The main thread (executing run()) has
* the responsibility to increment the progress appropriately.
*/
int progress();
}
The activation thread executes through the run() method,
incrementing the progress variable as well as generating partial
results (formatted as byte[]) during its execution. A monitor
thread is started to monitor the progress of activity, as well
as conformance to lease agreement. Periodically, the monitor
thread reads the partial results (if any) and communicates them
back to the LDAP server (after adding other fields of the
response) for returning as part results to the client. The
frequency at which partial results should be sent can be
controlled by the client-proxy by way of generating the results.
Goenka INTERNET DRAFT [Page 7]
<draft-ietf-ldapext-java-complex-search.txt> January 1998
7. ASN.1 Definition of Search Query Extension
This draft is the first attempt to capture all the required
attributes/interfaces of the extended request and response.
Comments on the design and utility of these definitions are
specifically invited from all reviewers.
The ASN.1 definition of extended operation as per LDAP (v3)
specification [2] is as follows :
ExtendedRequest ::= [APPLICATION 23] SEQUENCE {
requestName [0] LDAPOID,
requestValue [1] OCTET STRING OPTIONAL }
ExtendedResponse ::= [APPLICATION 24] SEQUENCE {
COMPONENTS OF LDAPResult,
responseName [10] LDAPOID OPTIONAL,
response [11] OCTET STRING OPTIONAL }
where, LDAPOID is a dotted-decimal representation of the OBJECT
IDENTIFIER corresponding to the request/response, and LDAPResult
corresponds to the final status (success/failure indications) of
the protocol operation request.
In the following section, the ASN.1 definition of request and
response values are presented.
requestValue ::= SEQUENCE {
leaseRequest LEASERequest,
ldap_sdk ENUMERATED {
JNDI (0),
LDAP_JavaAPI (1),
-- 2 to 5 reserved --
Proprietary (6) }
interface ClassName,
serializedObject OCTET STRING,
classes JavaARchive,
classURL [0] LDAP_URL OPTIONAL,
permissions [1] RequiredPermissions OPTIONAL }
LEASERequest ::= SEQUENCE {
estimatedDuration INTEGER (0 .. maxInt), -- in seconds --
maxDuration INTEGER (0 .. maxInt),
estimatedMemory INTEGER (0 .. maxInt), -- in KB --
maxMemory INTEGER (0 .. maxInt) }
RequiredPermissions ::= SEQUENCE {
permType ClassName,
permName OCTET STRING,
critical BOOLEAN DEFAULT TRUE,
actions [0] OCTET STRING OPTIONAL }
Goenka INTERNET DRAFT [Page 8]
<draft-ietf-ldapext-java-complex-search.txt> January 1998
ClassName ::= OCTET STRING
JavaARchive ::= OCTET STRING
- estimatedDuration -- duration in seconds, for which the
client-proxy must execute to generate any useful results.
- maxDuration -- the duration in seconds, which is the maximum
time the client-proxy would need to execute completely.
- estimatedMemory -- the memory requirement in KB, which the
client-proxy must have to execute.
- maxMemory -- the maximum amount of memory that the
client-proxy would ever need.
- interface -- the full name {package.class} of the
class/interface corresponding to the serialized object. This is
required by the server in order to appropriately deserialize the
object and invoke its methods.
- ldap_sdk -- the java LDAP implementation SDK to which the
serializedObject (client-proxy) is written. There are two
possible standards emerging, namely, JNDI (Java Naming and
Directory Interface) with LDAP binding, and java LDAP API [1].
It is expected that the server may already have the class files
corresponding to such standards, in which case these classes
need not be sent as part of the query. For clients which are
written to proprietary java LDAP implementation, the client may
send the entire LDAP implementation as a jar, as part of the
query, at the expense of the overhead involved. ASN.1 OIDs
might be a better alternative for specifying the ldap_sdk than
the current method via enumeration. Comments.
- serializedObject -- the serialized java object which
encapsulates the state and methods to execute the search query
on the server. There is only one root object (implementing the
given interface), which would be the entry point for execution.
The root object may have references to other objects (deep copy
of non-transient references) which are preserved during
serialization.
- classes -- the supporting class definitions (java byte code)
for all the classes required to de- serialize and execute the
client-proxy. This may include java implementations of LDAP, if
the server doesn't support the ldap_sdk to which the
client-proxy is written. The classes are packaged in a JAR (java
archive), in the standard JAR format.
- classURL -- specifies (optionally) the URL reference for the
Goenka INTERNET DRAFT [Page 9]
<draft-ietf-ldapext-java-complex-search.txt> January 1998
class definitions that might be required for executing the
client-proxy. This would include class definitions for
proprietary java LDAP implementations. The Server may NOT
support downloading classes from a URL, in which case an
appropriate error is returned.
- permissions -- these correspond to java permissions that might
be required by a client-proxy to execute. By default, the
client-proxy may have a minimal set of permissions grant
(similar to a restricted applet). Any specific permission must
be approved by the server. This model assumes the jdk1.2
security architecture with respect to permissions. The
permission requests have the following structure :
- permType -- the java permission class governing the
required permission. e.g., java.lang.RuntimePermission,
java.io.FilePermission etc.
- permName -- the name of the permission or first argument
to the appropriate permission class, such as host name
(for java.net.SocketPermission), createClassLoader (for
java.lang.RuntimePermission)
- critical -- determines whether this permission is a must
for the client-proxy to execute. All critical permissions
must be granted by the server, in order to execute the
client-proxy.
- actions -- second argument that some permissions take.
e.g., for java.io.FilePermission the allowed actions are
read, write, execute, delete. Some permissions do not take
a third argument (such as java.lang.RuntimePermission),
and hence this is an optional argument.
The ASN.1 definition for the extended response value follows :
response ::= SEQUENCE {
COMPONENTS OF LDAPExtendedResult,
leaseGrant LEASEGrant,
ldap_sdk_supported [0] ENUMERATED {
JNDI (0),
LDAP_JavaAPI (1),
-- 2 to 5 reserved --
} OPTIONAL
resultValue [1] OCTET STRING OPTIONAL
resultDone BOOLEAN DEFAULT FALSE }
LEASEGrant ::= SEQUENCE {
duration INTEGER (0 .. maxInt), -- in seconds --
memory INTEGER (0 .. maxInt) } -- in KB --
LDAPExtendedResult ::= SEQUENCE {
Goenka INTERNET DRAFT [Page 10]
<draft-ietf-ldapext-java-complex-search.txt> January 1998
resultCode ENUMERATED {
success (0),
leaseExpired (1),
resourceUseExceeded (2),
securityViolation (3),
noActivity (4),
permissionDenied (5),
dataError (6),
serverBusy (7),
leaseRenewed (8),
leaseGranted (9),
URL_ReferenceNotSupported (10),
-- 11-30 unused --
other (31) }
operationAbort BOOLEAN DEFAULT TRUE,
description OCTET STRING OPTIONAL }
- LDAPExtendedResult -- these return codes are specific to this
extension and are in addition to the more general LDAPResult
codes. They are used to communicate errors specific to the java
execution of the client-proxy. The above enumerated list is
clearly non-exhaustive, and have obvious meanings. If an error
results in the abortion of client-proxy, the operationAbort flag
is set true. description provides additional textual information
about the error, such as the stack trace in case of an
exception.
- LEASEGrant -- the duration (in seconds) and the memory (in
KB) for which the lease is granted by the server. In case of a
lease renewal, these values are in addition to the values or
previous lease grants.
- ldap_sdk_supported -- the LDAP APIs supported by the server. A
server may use this to communicate all SDKs that it supports.
- resultValue -- the result value is generated by the
client-proxy, to be consumed only by the client, and hence can
have any proprietary format, including but not limited to
existing LDAP response formats, or even java object(s) etc.
- resultDone -- when false, denotes that this is a partial
result, and more partial results would follow. When true,
denotes that this is the last and final part of the result. This
allows the client- proxy to generate partial results, as
appropriate, and communicate them to the client.
8. Implementation Considerations
To make use of this proposal, the LDAP server should be capable
of invoking a JVM, and should implement the proposed LDAP
extension. Java LDAP APIs should be standardized and the client
Goenka INTERNET DRAFT [Page 11]
<draft-ietf-ldapext-java-complex-search.txt> January 1998
should be written to them. The LDAP clients should be enabled
to send a search query encapsulated as a serialized java object
using the LDAP extension API. Java Security Architecture version
1.2 is assumed for associating specific permissions with
client-proxy code.
9. Acknowledgements
Thanks are due to Brian Jarvis and Vipul Modi for their
contributions to this work.
10. References
[1] R. Weltman, T. Howes, M. Smith, Christine Ho, "The
Java LDAP Application Program Interface", Internet Draft
draft-ietf-ldapext-ldap-java-api- 02.txt, July 1998.
[2] M. Wahl, T. Howes, S. Kille, "Lightweight Directory
Access Protocol (v3)", Internet Draft
draft-ietf-asid-ldapv3-protocol-04.txt, March 1997.
[3] T. Howes, "A String Representation of LDAP Search
Filters," RFC 1960, June 1996.
[4] A. Herron, T. Howes, M. Wahl, C.Weider, A. Anantha,
"LDAP Control Extension for Server Side Sorting of Search
Results", Internet Draft draft-ietf-ldapext-sorting-01.txt,
August, 1998
[5] David Boreham, Chris Weider, "LDAP Extensions for
Scrolling View Browsing of Search Results", Internet Draft,
draft-ietf-ldapext-ldapv3- vlv-01.txt, March, 1998
[6] Sun Microsystems, Inc. "Distributed Leasing
Specification", Whitepaper (JINI), lease.pdf, Revision 1.0 Beta,
July, 1998
11. Author's Address
Vishal Goenka
Novell, Inc.
122 East, 1700 South
Provo, UT 84606
USA
Phone: +1 801 861 4573
Fax: +1 801 861 2522
Email: vgoenka@novell.com
Goenka INTERNET DRAFT [Page 12]
