Search request BER parser incorrectly parses complex filters.

• Key: DIRSERVER-193
• Type: Bug
• Status: Closed
• Resolution: Fixed
• Priority: Blocker
• Assignee: Alex Karasulu
• Reporter: Jacob S. Barrett
• Component/s: ldap
• Affects Version/s: pre-1.0
• Fix Version/s: pre-1.0

Description

Using the following search from an LDAP client, like Softera's browser or OpenLDAP's ldapsearch, search for something like the following filter:

(& (a=A) (| (b=B) (c=C) ) )

The resulting expression object after the BER parser is finished is:

(& (| (c=C) (b=B) (a=A) ) )

This is obviously not the correct expression and results in bobus results.

I thought at first it might have been the expression object serializing to a string form that had issue, but passing the same filter string through the commons.filter.FilterParserImpl produces the correct expression object and the correct serialized string.

I am attempting to debug the problem further. If I can produce a patch I will post it, but if someone has a better idea of what is going please tackle this.

Comments

[Alex Karasulu]

Have not had the time yet to look at this one but if you're right this is really serious. We cannot release 0.9 without it. Can you attach a patch with a test case showing this bug in effect? If you are printing it out into a string it might be the visitor that prints out the info or the normalizing visitor that is causing this. The normalizing visitor tries to rearrange the AST for the filter so terms in the same nesting level are in the same cannonical order when printed out - this is done to be able to compare filter expressions.

[Alex Karasulu]

Actually scratch my last comment - I'm on it. Could not help myself :).

[Jacob S. Barrett]

I will keep digging at it too. So far what I have found is that when commons.berlib.asn1.decoder.search.OrRule.finish() is called it pops all the expressions off the stack. On the stack are all three equality expressions are on the stack. It appears as though there is no scoping. The (a=A) expression should not be within the scope of the OrRule.

Hope this helps you narrow it down faster. I am still trying to come up to speed on all this code.

[Alex Karasulu]

I tried to reproduce the bug but could not. I added the test case to on committed revision 158968. Here's the commit diff in the repo:

http://svn.apache.org/viewcvs.cgi?rev=158968&view=rev

[Alex Karasulu]

Ahhh ok you're going through ASN.1 ok I see.

[Jacob S. Barrett]

The AndRule.finish() is being called after the OrRule.finish() in my example. For some reason the decoder is not sensing the end of the AndRule until after it has processed the OrRule. I need to brush up on ASN.1 a bit more I guess. It seems like something is wrong with detecting the end of a SET.

[Alex Karasulu]

Just got back from dinner. I think I figured this out. Basically the AND/OR nodes keep eating from the top of the stack until there is no longer an ExprNode left. This is because there can be 2 or more subexpressions in these kinds of nodes. So what is happening is the OR rule is eating the expression a=A.

I just need a separator object between them so I know when to stop eating from the digester stack.

BTW this is very very nasty code. We are planing for a revamp soon so don't beat yourself for not understanding it. I wrote this in a hurry to get rid of a snacc4j dependency which blocked our incubator exit.

[Jacob S. Barrett]

I think this fixes it. It isn't the most pretty. Should probably replace the Stack with LinkedList to get rid of the synchronizations, but I want to go play poker now. I will post a better fix tomorrow some time. Thanks for your help.

[Alex Karasulu]

Jacob good fast fix but I took another approach. Regardless the patch was much appreciated. Keep flushing out those bugs you're really knocking them out. Enjoy poker :).

Committed in revision 158987:

http://svn.apache.org/viewcvs.cgi?rev=158987&view=rev

[Jacob S. Barrett]

I hate to be a pest but there is still a problem. The ExprNodes are added in the reverse order. If a rule was ordered specifically to match faster that optimization will be lost. With your fix it would be more appropriate to call BranchNode.addNodeToHead(ExprNode).

[Jacob S. Barrett]

This patch removes so debug code left in and corrects the oder of the ExprNodes. I thought about fixing the obvious performance hit of shifting the ArrayList elements every time an expression is added, but you said that all this BER parser code is going to get reworked. I will keep it in the back of my mind though.

[Alex Karasulu]

No problem at all. Can you supply a patch based on the changes I've made. I'll look at it and apply it immediately. This is why I have to use the BranchNormalizingVisitor to rearrange nodes for comparisons.

[Alex Karasulu]

Is this second patch applied after I made the changes? Meaning did you update then fix the rearrangement problem then generate the patch?

[Alex Karasulu]

Nevermind my last comment - I stopped being lazy and just looked inside the patch. I see what you did and applied the patch here in committed revision 159053:

http://svn.apache.org/viewcvs.cgi?rev=159053&view=revhttp://svn.apache.org/viewcvs.cgi?rev=159053&view=rev

Thanks!

Closing all issues created in 2005 and before which are marked resolved