You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@directory.apache.org by Apache Wiki <wi...@apache.org> on 2005/06/14 01:48:55 UTC
[Directory Wiki] Update of "Asn1Home" by EmmanuelLecharny
Dear Wiki user,
You have subscribed to a wiki page or wiki category on "Directory Wiki" for change notification.
The following page has been changed by EmmanuelLecharny:
http://wiki.apache.org/directory/Asn1Home
The comment on the change is:
Updated this page, adding some information about LDAP and cleaning stuff.
------------------------------------------------------------------------------
##language:en
- == ASN.1 encoder/decoder ==
+ = ASN.1 encoder/decoder =
- This page is just a blackboard, to throw ideas. They may be duplication of other pieces of documentation.
+
+ == Table Of Contents ==
+
+ [[TableOfContents]]
== Components ==
@@ -64, +67 @@
Ideally, they are generated by an '''ASN.1''' compiler, but can be hand crafted.
- === TLVs ===
+ === PDU and TLVs ===
+
+ PDU stands for '''P'''acket '''D'''ata '''U'''nit. An ASN.1 encoded element is stored in a PDU. This is what is transfered between a client and a server.
+
+ TLV stands for '''Type/Length/Value'''. A PDU is made of '''TLV'''s. Each '''TLV''' represent either a primitive element, and it has a '''V'''alue, or a constructed element, and the '''V'''alue is itself one ore more '''TLV''' (The '''V''' can contain more than one '''TLV'''). The '''PDU''' structure is like a tree, where the '''PDU''' is the whole tree, and where '''TLV''' are leaves (primitives) and branches (constructed)
+
+ Further information about '''TLV'''s can be found here :
* ["TLVPageInfo"]: Informations about '''Tlv'''s
+ === Buffer ===
+ Buffering the incoming request or the ourgoing response is essential. As a request or a response can be hudge (for exampole, if we want to store images), it is necessary to store bytes in buffers in order to be able to pipeline the processing. Flushing informations byte by byte is totally insane, from the network point of view.
+
+ We are using the '''NIO''' '''ByteBuffer''' structure to store chunks of information, before pushing them on the network, and reversly, store incoming bytes into buffers before processing the request.
+
=== IO ===
+ For any information, the best place is certainly ["MinaHome"]
== Processing ==
+ There are two kind of processing : '''encoding''' and '''decoding'''. Encoding is quite easy, decoding is much more complicated.
+
+ {{{
+ Important : decoding an ASN.1 PDU is generally not possible if you have no knowledge of the grammar being decoded. To limit the size of PDUs, the encoding schemes used (PER, DER, BER, ...) permit the elimination of some TL if the constructed TLV that encapsulate the previous one is unambiguiously known. One who want to decode a PDU *MUST* know which grammar has been used.
+ }}}
+
=== Encoder ===
+ The encoding process is quite easy. As we know what has to be encoded, the structure of the PDU is somehow dependent on the structure of the POJO which contains the data. The only tricky things is the '''Length''' part, which has to be computed. As a '''TLV''' may have a '''V''' part which is itself one or more '''TLV'''s, its '''L''' part will be the sum of each '''TLV'''s length. This is typically a recursive processing, but we can also process the POJO in two passes :
+ * the first pass compute each length
+ * the second pass generate the '''PDU'''
+
+ This is the way it's done.
+
=== Decoder ===
- The decoding process is an infinite loop that can read a PDU. A PDU is composed of TLVs which could have sub-TLVs and so on.
+ The decoding process is an infinite loop that can read a '''PDU'''.
+ TODO
=== Performance ===
TODO : performance against memory/scalability/failover
@@ -202, +230 @@
== LDAP ASN.1 State Automaton ==
- LDAP Grammar can be seen as a State Automaton. It starts with the following diagram :
+ === LDAP ASN.1 Grammar ===
+ The LDAP ASN.1 Grammar is described in RFC 2251. Here is the grammar :
+
+ {{{
+ -- Lightweight-Directory-Access-Protocol-V3 DEFINITIONS
+ -- See rfc2251
+ --
+ -- (c) LDAPd Group
+ -- Please refer to the LICENSE.txt file in the root directory of
+ -- any LDAPd project for copyright and distribution information.
+ --
+ -- $Id: ldapv3.asn1,v 1.2 2003/03/13 18:06:06 akarasulu Exp $
+ -- $Author: akarasulu $
+
+
+ LDAP-V3 DEFINITIONS
+ IMPLICIT TAGS ::= --pragma {packagePrefix: "ldapd.common.ber"}
+
+ BEGIN
+
+ LDAPMessage ::= SEQUENCE {
+ messageID MessageID,
+ protocolOp CHOICE {
+ bindRequest BindRequest,
+ bindResponse BindResponse,
+ unbindRequest UnbindRequest,
+ searchRequest SearchRequest,
+ searchResEntry SearchResultEntry,
+ searchResDone SearchResultDone,
+ searchResRef SearchResultReference,
+ modifyRequest ModifyRequest,
+ modifyResponse ModifyResponse,
+ addRequest AddRequest,
+ addResponse AddResponse,
+ delRequest DelRequest,
+ delResponse DelResponse,
+ modDNRequest ModifyDNRequest,
+ modDNResponse ModifyDNResponse,
+ compareRequest CompareRequest,
+ compareResponse CompareResponse,
+ abandonRequest AbandonRequest,
+ extendedReq ExtendedRequest,
+ extendedResp ExtendedResponse },
+ controls [0] Controls OPTIONAL }
+
+ MessageID ::= INTEGER (0 .. maxInt)
+
+ maxInt INTEGER ::= 2147483647 -- (2^^31 - 1) --
+
+ LDAPString ::= OCTET STRING
+
+ LDAPOID ::= OCTET STRING
+
+ LDAPDN ::= LDAPString
+
+ RelativeLDAPDN ::= LDAPString
+
+ AttributeType ::= LDAPString
+
+ AttributeDescription ::= LDAPString
+
+ AttributeDescriptionList ::= SEQUENCE OF
+ AttributeDescription
+
+ AttributeValue ::= OCTET STRING
+
+ AttributeValueAssertion ::= SEQUENCE {
+ attributeDesc AttributeDescription,
+ assertionValue AssertionValue }
+
+ AssertionValue ::= OCTET STRING
+
+ Attribute ::= SEQUENCE {
+ type AttributeDescription,
+ vals SET OF AttributeValue }
+
+ MatchingRuleId ::= LDAPString
+
+ LDAPResult ::= SEQUENCE {
+ resultCode ENUMERATED {
+ success (0),
+ operationsError (1),
+ protocolError (2),
+ timeLimitExceeded (3),
+ sizeLimitExceeded (4),
+ compareFalse (5),
+ compareTrue (6),
+ authMethodNotSupported (7),
+ strongAuthRequired (8),
+ -- 9 reserved --
+ referral (10), -- new
+ adminLimitExceeded (11), -- new
+ unavailableCriticalExtension (12), -- new
+ confidentialityRequired (13), -- new
+ saslBindInProgress (14), -- new
+ noSuchAttribute (16),
+ undefinedAttributeType (17),
+ inappropriateMatching (18),
+ constraintViolation (19),
+ attributeOrValueExists (20),
+ invalidAttributeSyntax (21),
+ -- 22-31 unused --
+ noSuchObject (32),
+ aliasProblem (33),
+ invalidDNSyntax (34),
+ -- 35 reserved for undefined isLeaf --
+ aliasDereferencingProblem (36),
+ -- 37-47 unused --
+ inappropriateAuthentication (48),
+ invalidCredentials (49),
+ insufficientAccessRights (50),
+ busy (51),
+ unavailable (52),
+ unwillingToPerform (53),
+ loopDetect (54),
+ -- 55-63 unused --
+ namingViolation (64),
+ objectClassViolation (65),
+ notAllowedOnNonLeaf (66),
+ notAllowedOnRDN (67),
+ entryAlreadyExists (68),
+ objectClassModsProhibited (69),
+ -- 70 reserved for CLDAP --
+ affectsMultipleDSAs (71), -- new
+ -- 72-79 unused --
+ other (80) },
+ -- 81-90 reserved for APIs --
+ matchedDN LDAPDN,
+ errorMessage LDAPString,
+ referral [3] Referral OPTIONAL }
+
+ Referral ::= SEQUENCE OF LDAPURL
+
+ LDAPURL ::= LDAPString -- limited to characters permitted in URLs
+
+ Controls ::= SEQUENCE OF Control
+
+ Control ::= SEQUENCE {
+ controlType LDAPOID,
+ criticality BOOLEAN DEFAULT FALSE,
+ controlValue OCTET STRING OPTIONAL }
+
+ BindRequest ::= [APPLICATION 0] SEQUENCE {
+ version INTEGER (1 .. 127),
+ name LDAPDN,
+ authentication AuthenticationChoice }
+
+ AuthenticationChoice ::= CHOICE {
+ simple [0] OCTET STRING,
+ -- 1 and 2 reserved
+ sasl [3] SaslCredentials }
+
+ SaslCredentials ::= SEQUENCE {
+ mechanism LDAPString,
+ credentials OCTET STRING OPTIONAL }
+
+ BindResponse ::= [APPLICATION 1] SEQUENCE {
+
+ COMPONENTS OF LDAPResult,
+ serverSaslCreds [7] OCTET STRING OPTIONAL }
+
+ UnbindRequest ::= [APPLICATION 2] NULL
+
+ SearchRequest ::= [APPLICATION 3] SEQUENCE {
+ baseObject LDAPDN,
+ scope ENUMERATED {
+ baseObject (0),
+ singleLevel (1),
+ wholeSubtree (2) },
+ derefAliases ENUMERATED {
+ neverDerefAliases (0),
+ derefInSearching (1),
+ derefFindingBaseObj (2),
+ derefAlways (3) },
+ sizeLimit INTEGER (0 .. maxInt),
+ timeLimit INTEGER (0 .. maxInt),
+ typesOnly BOOLEAN,
+ filter Filter,
+ attributes AttributeDescriptionList }
+
+ Filter ::= CHOICE {
+ and [0] SET OF Filter,
+ or [1] SET OF Filter,
+ not [2] Filter,
+ equalityMatch [3] AttributeValueAssertion,
+ substrings [4] SubstringFilter,
+ greaterOrEqual [5] AttributeValueAssertion,
+ lessOrEqual [6] AttributeValueAssertion,
+ present [7] AttributeDescription,
+ approxMatch [8] AttributeValueAssertion,
+ extensibleMatch [9] MatchingRuleAssertion }
+
+ SubstringFilter ::= SEQUENCE {
+ type AttributeDescription,
+ -- at least one must be present
+ substrings SEQUENCE OF CHOICE {
+ initial [0] LDAPString,
+ any [1] LDAPString,
+ final [2] LDAPString } }
+
+ MatchingRuleAssertion ::= SEQUENCE {
+ matchingRule [1] MatchingRuleId OPTIONAL,
+ type [2] AttributeDescription OPTIONAL,
+ matchValue [3] AssertionValue,
+ dnAttributes [4] BOOLEAN DEFAULT FALSE }
+
+ SearchResultEntry ::= [APPLICATION 4] SEQUENCE {
+ objectName LDAPDN,
+ attributes PartialAttributeList }
+
+ PartialAttributeList ::= SEQUENCE OF SEQUENCE {
+ type AttributeDescription,
+ vals SET OF AttributeValue }
+
+ SearchResultReference ::= [APPLICATION 19] SEQUENCE OF LDAPURL
+
+ SearchResultDone ::= [APPLICATION 5] LDAPResult
+
+ ModifyRequest ::= [APPLICATION 6] SEQUENCE {
+ object LDAPDN,
+ modification SEQUENCE OF SEQUENCE {
+ operation ENUMERATED {
+ add (0),
+ delete (1),
+ replace (2) },
+ modification AttributeTypeAndValues } }
+
+ AttributeTypeAndValues ::= SEQUENCE {
+ type AttributeDescription,
+ vals SET OF AttributeValue }
+
+ ModifyResponse ::= [APPLICATION 7] LDAPResult
+
+ AddRequest ::= [APPLICATION 8] SEQUENCE {
+ entry LDAPDN,
+ attributes AttributeList }
+
+ AttributeList ::= SEQUENCE OF SEQUENCE {
+ type AttributeDescription,
+ vals SET OF AttributeValue }
+
+ AddResponse ::= [APPLICATION 9] LDAPResult
+
+ DelRequest ::= [APPLICATION 10] LDAPDN
+
+ DelResponse ::= [APPLICATION 11] LDAPResult
+
+ ModifyDNRequest ::= [APPLICATION 12] SEQUENCE {
+ entry LDAPDN,
+ newrdn RelativeLDAPDN,
+ deleteoldrdn BOOLEAN,
+ newSuperior [0] LDAPDN OPTIONAL }
+
+ ModifyDNResponse ::= [APPLICATION 13] LDAPResult
+
+ CompareRequest ::= [APPLICATION 14] SEQUENCE {
+ entry LDAPDN,
+ ava AttributeValueAssertion }
+
+ CompareResponse ::= [APPLICATION 15] LDAPResult
+
+ AbandonRequest ::= [APPLICATION 16] MessageID
+
+ 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 }
+
+ END
+ }}}
+
+ As one can see, it's much more complicated than the SPNEGO grammar ! The used encoding is a subset of BER, where the TRUE value is always encoded as 0xFF and where all length are fully definite.
+
+ === Decoding an LDAP message ===
+ Each LDAP message starts with a first automate :
+
- attachment:ldapMessage.png
+ attachment:LdapMessage.png
The next part (''protocol``Op'') will contains all the different type of possible messages. :
@@ -214, +521 @@
It can be followed by an optionnal control part, which automaton state is shown below :
- attachment:controls.png
+ attachment:Controls.png
Those two states automaton will be implemented as a Grammar instance, which will be processed for each LdapMessage we will receive. When we will know which kind of Message we have to deal with, a new Grammar will be loaded and processed (a Bind``Request grammar, or a Bind``Response...). If the specific message is correctly decoded, we may have to load the Controls grammar. So the engine switch from grammar to grammar depending on which part it is decoding. This is implemented by a Grammar stack which is stored in the decoder Container.
@@ -222, +529 @@
Many Ldap``Message while return a result. A specific sub-diagram is dedicated to this Ldap``Result :
- attachment:ldapResult.png
+ attachment:LdapResult.png
We have a specific Grammar to process this LdapResult.
@@ -230, +537 @@
The Bind``Request Ldap Message state diagram is shown below :
- attachment:bindRequest.png
+ attachment:BindRequest.png
The decoding of a Bind``Request message is simple, as we just need to build an engine that walks through the state automaton, checking at each state that the next transition is valid, and execute the associated action. In the real world, it's a little bit more complicated, because states are not those that we have in the pictures. We have to split each 'state' to sub-states : one sub-state for the '''Type''', one sub-state for the '''Length''' and another one for the '''Value''', if necessary.
@@ -244, +551 @@
The Ldap Bind``Response message is also made up of four elements : a ''Ldap``Message'', the ''Bind``Response'', a ''Ldap``Result'' element and optionnaly a final ''Controls''. Here is the inner ''Bind``Response'' element :
- attachment:bindResponse.png
+ attachment:BindResponse.png
+ === UnBindRequest ===
+
+ This is the simplest automate! It is fully described in the protocol``OP schema.
+
+ attachement:UnBindRequest.png
+
+ === AbandonRequest ===
+
+ This LDAP message is sent by a user when he want the current operation to abort (if a search request take too long, for instance).
+
+ This request just send the Message id which has to be stopped.
+
+ attachement:AbandonRequest.png
+
+ === SearchRequest ===
+
+ The heart of LDAP. Search request are quite complicated, as LDAP is mainly used to search information. We will use four different automatons to express this part of the LDAP grammar :
+
+ attachement:SearchRequest.png
+ attachement:Filter.png
+ attachement:SubstringFilter.png
+ attachement:MatchingRuleAssertion.png
+