OpenLDAP
Up to top level
Build   Contrib   Development   Documentation   Historical   Incoming   Software Bugs   Software Enhancements   Web  

Logged in as guest

Viewing Incoming/6683
Full headers

From: petteri.stenius@ubisecure.com
Subject: DDS fails with expired branches
Compose comment
Download message
State:
0 replies:
3 followups: 1 2 3

Major security issue: yes  no

Notes:

Notification:


Date: Mon, 25 Oct 2010 10:34:53 +0000
From: petteri.stenius@ubisecure.com
To: openldap-its@OpenLDAP.org
Subject: DDS fails with expired branches
Full_Name: 
Version: 2.4.23
OS: Linux
URL: ftp://ftp.openldap.org/incoming/
Submission from: (NULL) (195.197.205.34)


Hello,

I have a directory with branches of dynamicObject entries. It looks like if the
entryExpireTimestamp value is the same on objects within a branch then DDS
search for expired objects will only find the top-most object. This results in
remove failing with message

DDS dn="cn=top,cn=root,dc=test" is non-leaf; deferring.


To reproduce

OpenLDAP 2.4.23, Berkeley DB 4.6.21

Use slapadd to prepare directory with following

dn: cn=Root,dc=test
objectClass: top
objectClass: applicationProcess
cn: Root

dn: cn=top,cn=Root,dc=test
objectClass: top
objectClass: device
objectClass: dynamicObject
entryTTL: 60
entryExpireTimestamp: 20101024113626Z
cn: top

dn: cn=leaf1,cn=top,cn=Root,dc=test
objectClass: top
objectClass: device
objectClass: dynamicObject
entryTTL: 60
entryExpireTimestamp: 20101024113626Z
cn: leaf1

dn: cn=leaf2,cn=top,cn=Root,dc=test
objectClass: top
objectClass: device
objectClass: dynamicObject
entryTTL: 60
entryExpireTimestamp: 20101024113626Z
cn: leaf2

dn: cn=leaf3,cn=top,cn=Root,dc=test
objectClass: top
objectClass: device
objectClass: dynamicObject
entryTTL: 60
entryExpireTimestamp: 20101024113626Z
cn: leaf3


Relevant slapd.conf entries

database        bdb
suffix          "cn=Root,dc=test"
rootdn          "cn=Root,dc=test"
rootpw          "password"

overlay         dds
dds-default-ttl 3600
dds-min-ttl     60
dds-interval    60
dds-state       true
index           entryExpireTimestamp eq,pres

access to dn.subtree="cn=Root,dc=test"
        by users write
        by * read


Running "slapd -d 1 -d 256" produces following

put_filter: "(&(objectClass=dynamicObject)(entryExpireTimestamp<=20101025082446Z))"
put_filter: AND
put_filter_list "(objectClass=dynamicObject)(entryExpireTimestamp<=20101025082446Z)"
put_filter: "(objectClass=dynamicObject)"
put_filter: simple
put_simple_filter: "objectClass=dynamicObject"
put_filter: "(entryExpireTimestamp<=20101025082446Z)"
put_filter: simple
put_simple_filter: "entryExpireTimestamp<=20101025082446Z"
ber_scanf fmt ({mm}) ber:
ber_scanf fmt ({mm}) ber:
=> bdb_search
bdb_dn2entry("cn=root,dc=test")
=> bdb_dn2id("cn=root,dc=test")
<= bdb_dn2id: got id=0x1
entry_decode: "cn=Root,dc=test"
<= entry_decode(cn=Root,dc=test)
search_candidates: base="cn=root,dc=test" (0x00000001) scope=2
=> bdb_dn2idl("cn=root,dc=test")
=> bdb_equality_candidates (objectClass)
=> key_read
<= bdb_index_read: failed (-30989)
<= bdb_equality_candidates: id=0, first=0, last=0
=> bdb_equality_candidates (objectClass)
=> key_read
<= bdb_index_read 4 candidates
<= bdb_equality_candidates: id=4, first=2, last=5
=> bdb_inequality_candidates (entryExpireTimestamp)
=> key_read
<= bdb_index_read 1 candidates
=> key_read
<= bdb_index_read: failed (-30989)
<= bdb_inequality_candidates: id=1, first=2, last=2
bdb_search_candidates: id=1 first=2 last=2
entry_decode: "cn=top,cn=Root,dc=test"
<= entry_decode(cn=top,cn=Root,dc=test)
=> bdb_dn2id("cn=top,cn=root,dc=test")
<= bdb_dn2id: got id=0x2
send_ldap_result: conn=-1 op=0 p=0
bdb_dn2entry("cn=top,cn=root,dc=test")
=> bdb_dn2id_children("cn=top,cn=root,dc=test")
<= bdb_dn2id_children("cn=top,cn=root,dc=test"):  (0)
send_ldap_result: conn=-1 op=0 p=0
DDS dn="cn=top,cn=root,dc=test" is non-leaf; deferring.
DDS expired=0


ldapsearch "(entryExpireTimestamp=*)" produces

dn: cn=top,cn=Root,dc=test
entryExpireTimestamp: 20101024113626Z

dn: cn=leaf1,cn=top,cn=Root,dc=test
entryExpireTimestamp: 20101024113626Z

dn: cn=leaf2,cn=top,cn=Root,dc=test
entryExpireTimestamp: 20101024113626Z

dn: cn=leaf3,cn=top,cn=Root,dc=test
entryExpireTimestamp: 20101024113626Z


where ldapsearch "(entryExpireTimestamp<=20101024113626Z)" only finds

dn: cn=top,cn=Root,dc=test
entryExpireTimestamp: 20101024113626Z


If I change all timestamps to distinct values then expiration of complete
branches works as expected.


Thanks,
Petteri

Followup 1

Download message
Subject: RE: (ITS#6683) DDS fails with expired branches
Date: Tue, 9 Nov 2010 07:53:15 +0200
From: "Petteri Stenius" <Petteri.Stenius@ubisecure.com>
To: <openldap-its@openldap.org>
Hello,

Further investigation shows this issue is caused by operator LE search
failing with indexed attributes. Also this indexed search issue is NOT
limited to DDS.=20

I have reproduced the issue with integerOrderingMatch and
generalizedTimeOrderingMatch.=20

The piece of code I find suspicious is in servers/back-bdb/idl.c,
somewhere in the middle it reads

	/* skip presence key on range inequality lookups */
	while (rc =3D=3D 0 && kptr->size !=3D len) {
		rc =3D cursor->c_get( cursor, kptr, &data, flags |
DB_NEXT_NODUP );
	}

If I remove this block then LE search works as expected with indexed
attributes. The key here seems to be the DB_NEXT_NODUP flag. This flag
causes the iterator block a few lines below to return partial matches.

Thanks,
Petteri

-----Original Message-----
From: openldap-bugs-bounces@OpenLDAP.org
[mailto:openldap-bugs-bounces@OpenLDAP.org] On Behalf Of
petteri.stenius@ubisecure.com
Sent: Monday, October 25, 2010 1:35 PM
To: openldap-its@openldap.org
Subject: (ITS#6683) DDS fails with expired branches

Full_Name:=20
Version: 2.4.23
OS: Linux
URL: ftp://ftp.openldap.org/incoming/
Submission from: (NULL) (195.197.205.34)


Hello,

I have a directory with branches of dynamicObject entries. It looks like
if the
entryExpireTimestamp value is the same on objects within a branch then
DDS
search for expired objects will only find the top-most object. This
results in
remove failing with message

DDS dn=3D"cn=3Dtop,cn=3Droot,dc=3Dtest" is non-leaf; deferring.


To reproduce

OpenLDAP 2.4.23, Berkeley DB 4.6.21

Use slapadd to prepare directory with following

dn: cn=3DRoot,dc=3Dtest
objectClass: top
objectClass: applicationProcess
cn: Root

dn: cn=3Dtop,cn=3DRoot,dc=3Dtest
objectClass: top
objectClass: device
objectClass: dynamicObject
entryTTL: 60
entryExpireTimestamp: 20101024113626Z
cn: top

dn: cn=3Dleaf1,cn=3Dtop,cn=3DRoot,dc=3Dtest
objectClass: top
objectClass: device
objectClass: dynamicObject
entryTTL: 60
entryExpireTimestamp: 20101024113626Z
cn: leaf1

dn: cn=3Dleaf2,cn=3Dtop,cn=3DRoot,dc=3Dtest
objectClass: top
objectClass: device
objectClass: dynamicObject
entryTTL: 60
entryExpireTimestamp: 20101024113626Z
cn: leaf2

dn: cn=3Dleaf3,cn=3Dtop,cn=3DRoot,dc=3Dtest
objectClass: top
objectClass: device
objectClass: dynamicObject
entryTTL: 60
entryExpireTimestamp: 20101024113626Z
cn: leaf3


Relevant slapd.conf entries

database        bdb
suffix          "cn=3DRoot,dc=3Dtest"
rootdn          "cn=3DRoot,dc=3Dtest"
rootpw          "password"

overlay         dds
dds-default-ttl 3600
dds-min-ttl     60
dds-interval    60
dds-state       true
index           entryExpireTimestamp eq,pres

access to dn.subtree=3D"cn=3DRoot,dc=3Dtest"
        by users write
        by * read


Running "slapd -d 1 -d 256" produces following

put_filter:
"(&(objectClass=3DdynamicObject)(entryExpireTimestamp<=3D20101025082446Z)=
)"
put_filter: AND
put_filter_list
"(objectClass=3DdynamicObject)(entryExpireTimestamp<=3D20101025082446Z)"
put_filter: "(objectClass=3DdynamicObject)"
put_filter: simple
put_simple_filter: "objectClass=3DdynamicObject"
put_filter: "(entryExpireTimestamp<=3D20101025082446Z)"
put_filter: simple
put_simple_filter: "entryExpireTimestamp<=3D20101025082446Z"
ber_scanf fmt ({mm}) ber:
ber_scanf fmt ({mm}) ber:
=3D> bdb_search
bdb_dn2entry("cn=3Droot,dc=3Dtest")
=3D> bdb_dn2id("cn=3Droot,dc=3Dtest")
<=3D bdb_dn2id: got id=3D0x1
entry_decode: "cn=3DRoot,dc=3Dtest"
<=3D entry_decode(cn=3DRoot,dc=3Dtest)
search_candidates: base=3D"cn=3Droot,dc=3Dtest" (0x00000001) scope=3D2
=3D> bdb_dn2idl("cn=3Droot,dc=3Dtest")
=3D> bdb_equality_candidates (objectClass)
=3D> key_read
<=3D bdb_index_read: failed (-30989)
<=3D bdb_equality_candidates: id=3D0, first=3D0, last=3D0
=3D> bdb_equality_candidates (objectClass)
=3D> key_read
<=3D bdb_index_read 4 candidates
<=3D bdb_equality_candidates: id=3D4, first=3D2, last=3D5
=3D> bdb_inequality_candidates (entryExpireTimestamp)
=3D> key_read
<=3D bdb_index_read 1 candidates
=3D> key_read
<=3D bdb_index_read: failed (-30989)
<=3D bdb_inequality_candidates: id=3D1, first=3D2, last=3D2
bdb_search_candidates: id=3D1 first=3D2 last=3D2
entry_decode: "cn=3Dtop,cn=3DRoot,dc=3Dtest"
<=3D entry_decode(cn=3Dtop,cn=3DRoot,dc=3Dtest)
=3D> bdb_dn2id("cn=3Dtop,cn=3Droot,dc=3Dtest")
<=3D bdb_dn2id: got id=3D0x2
send_ldap_result: conn=3D-1 op=3D0 p=3D0
bdb_dn2entry("cn=3Dtop,cn=3Droot,dc=3Dtest")
=3D> bdb_dn2id_children("cn=3Dtop,cn=3Droot,dc=3Dtest")
<=3D bdb_dn2id_children("cn=3Dtop,cn=3Droot,dc=3Dtest"):  (0)
send_ldap_result: conn=3D-1 op=3D0 p=3D0
DDS dn=3D"cn=3Dtop,cn=3Droot,dc=3Dtest" is non-leaf; deferring.
DDS expired=3D0


ldapsearch "(entryExpireTimestamp=3D*)" produces

dn: cn=3Dtop,cn=3DRoot,dc=3Dtest
entryExpireTimestamp: 20101024113626Z

dn: cn=3Dleaf1,cn=3Dtop,cn=3DRoot,dc=3Dtest
entryExpireTimestamp: 20101024113626Z

dn: cn=3Dleaf2,cn=3Dtop,cn=3DRoot,dc=3Dtest
entr

Message of length 5389 truncated


Followup 2

Download message
Date: Tue, 09 Nov 2010 00:45:09 -0800
From: Howard Chu <hyc@symas.com>
To: Petteri.Stenius@ubisecure.com
CC: openldap-its@openldap.org
Subject: Re: (ITS#6683) DDS fails with expired branches
Petteri.Stenius@ubisecure.com wrote:
> Hello,
>
> Further investigation shows this issue is caused by operator LE search
> failing with indexed attributes. Also this indexed search issue is NOT
> limited to DDS.=20
>
> I have reproduced the issue with integerOrderingMatch and
> generalizedTimeOrderingMatch.=20
>
> The piece of code I find suspicious is in servers/back-bdb/idl.c,
> somewhere in the middle it reads
>
> 	/* skip presence key on range inequality lookups */
> 	while (rc =3D=3D 0&&  kptr->size !=3D len) {
> 		rc =3D cursor->c_get( cursor, kptr,&data, flags |
> DB_NEXT_NODUP );
> 	}
>
> If I remove this block then LE search works as expected with indexed
> attributes. The key here seems to be the DB_NEXT_NODUP flag. This flag
> causes the iterator block a few lines below to return partial matches.

That implies that there's something else corrupt in the index, because the 
presence key will never be the same size as an equality key.

>
> Thanks,
> Petteri
>
> -----Original Message-----
> From: openldap-bugs-bounces@OpenLDAP.org
> [mailto:openldap-bugs-bounces@OpenLDAP.org] On Behalf Of
> petteri.stenius@ubisecure.com
> Sent: Monday, October 25, 2010 1:35 PM
> To: openldap-its@openldap.org
> Subject: (ITS#6683) DDS fails with expired branches
>
> Full_Name:=20
> Version: 2.4.23
> OS: Linux
> URL: ftp://ftp.openldap.org/incoming/
> Submission from: (NULL) (195.197.205.34)
>
>
> Hello,
>
> I have a directory with branches of dynamicObject entries. It looks like
> if the
> entryExpireTimestamp value is the same on objects within a branch then
> DDS
> search for expired objects will only find the top-most object. This
> results in
> remove failing with message
>
> DDS dn=3D"cn=3Dtop,cn=3Droot,dc=3Dtest" is non-leaf; deferring.
>
>
> To reproduce
>
> OpenLDAP 2.4.23, Berkeley DB 4.6.21
>
> Use slapadd to prepare directory with following
>
> dn: cn=3DRoot,dc=3Dtest
> objectClass: top
> objectClass: applicationProcess
> cn: Root
>
> dn: cn=3Dtop,cn=3DRoot,dc=3Dtest
> objectClass: top
> objectClass: device
> objectClass: dynamicObject
> entryTTL: 60
> entryExpireTimestamp: 20101024113626Z
> cn: top
>
> dn: cn=3Dleaf1,cn=3Dtop,cn=3DRoot,dc=3Dtest
> objectClass: top
> objectClass: device
> objectClass: dynamicObject
> entryTTL: 60
> entryExpireTimestamp: 20101024113626Z
> cn: leaf1
>
> dn: cn=3Dleaf2,cn=3Dtop,cn=3DRoot,dc=3Dtest
> objectClass: top
> objectClass: device
> objectClass: dynamicObject
> entryTTL: 60
> entryExpireTimestamp: 20101024113626Z
> cn: leaf2
>
> dn: cn=3Dleaf3,cn=3Dtop,cn=3DRoot,dc=3Dtest
> objectClass: top
> objectClass: device
> objectClass: dynamicObject
> entryTTL: 60
> entryExpireTimestamp: 20101024113626Z
> cn: leaf3
>
>
> Relevant slapd.conf entries
>
> database        bdb
> suffix          "cn=3DRoot,dc=3Dtest"
> rootdn          "cn=3DRoot,dc=3Dtest"
> rootpw          "password"
>
> overlay         dds
> dds-default-ttl 3600
> dds-min-ttl     60
> dds-interval    60
> dds-state       true
> index           entryExpireTimestamp eq,pres
>
> access to dn.subtree=3D"cn=3DRoot,dc=3Dtest"
>          by users write
>          by * read
>
>
> Running "slapd -d 1 -d 256" produces following
>
> put_filter:
> "(&(objectClass=3DdynamicObject)(entryExpireTimestamp<=3D20101025082446Z)=
> )"
> put_filter: AND
> put_filter_list
> "(objectClass=3DdynamicObject)(entryExpireTimestamp<=3D20101025082446Z)"
> put_filter: "(objectClass=3DdynamicObject)"
> put_filter: simple
> put_simple_filter: "objectClass=3DdynamicObject"
> put_filter: "(entryExpireTimestamp<=3D20101025082446Z)"
> put_filter: simple
> put_simple_filter: "entryExpireTimestamp<=3D20101025082446Z"
> ber_scanf fmt ({mm}) ber:
> ber_scanf fmt ({mm}) ber:
> =3D>  bdb_search
> bdb_dn2entry("cn=3Droot,dc=3Dtest")
> =3D>  bdb_dn2id("cn=3Droot,dc=3Dtest")
> <=3D bdb_dn2id: got id=3D0x1
> entry_decode: "cn=3DRoot,dc=3Dtest"
> <=3D entry_decode(cn=3DRoot,dc=3Dtest)
> search_candidates: base=3D"cn=3Droot,dc=3Dtest" (0x00000001) scope=3D2
> =3D>  bdb_dn2idl("cn=3Droot,dc=3Dtest")
> =3D>  bdb_equality_candidates (objectClass)
> =3D>  key_read
> <=3D bdb_index_read: failed (-30989)
> <=3D bdb_equality_candidates: id=3D0, first=3D0, last=3D0
> =3D>  bdb_equality_candidates (objectClass)
> =3D>  key_read
> <=3D bdb_index_read 4 candidates
> <=3D bdb_equality_candidates: id=3D4, first=3D2, last=3D5
> =3D>  bdb_inequality_candidates (entryExpireTimestamp)
> =3D>  key_read
> <=3D bdb_index_read 1 candidates
> =3D>  key_rea

Message of length 6726 truncated


Followup 3

Download message
Subject: RE: (ITS#6683) DDS fails with expired branches
Date: Wed, 10 Nov 2010 13:26:49 +0200
From: "Petteri Stenius" <Petteri.Stenius@ubisecure.com>
To: "Howard Chu" <hyc@symas.com>, <openldap-its@openldap.org>
Hi,

Thank you for your reply.

My knowledge about the bdb internals is limited. I have reproduced this
issue and reduced it to a small amount of data (see below). I think I
have done everything right with regards to setting up and preparing the
database and indexes. I've used both ldapmodify and slapadd/slapindex to
prepare the db.

If you think my indexes are corrupt then can you please give me pointers
how to verify?

I don't think there exist test cases for operators LE "<=3D" or GE =
">=3D" in
the source codes.

Thanks,
Petteri

-----Original Message-----
From: Howard Chu [mailto:hyc@symas.com]=20
Sent: Tuesday, November 09, 2010 10:45 AM
To: Petteri Stenius
Cc: openldap-its@openldap.org
Subject: Re: (ITS#6683) DDS fails with expired branches

Petteri.Stenius@ubisecure.com wrote:
> Hello,
>
> Further investigation shows this issue is caused by operator LE search
> failing with indexed attributes. Also this indexed search issue is NOT
> limited to DDS.=3D20
>
> I have reproduced the issue with integerOrderingMatch and
> generalizedTimeOrderingMatch.=3D20
>
> The piece of code I find suspicious is in servers/back-bdb/idl.c,
> somewhere in the middle it reads
>
> 	/* skip presence key on range inequality lookups */
> 	while (rc =3D3D=3D3D 0&&  kptr->size !=3D3D len) {
> 		rc =3D3D cursor->c_get( cursor, kptr,&data, flags |
> DB_NEXT_NODUP );
> 	}
>
> If I remove this block then LE search works as expected with indexed
> attributes. The key here seems to be the DB_NEXT_NODUP flag. This flag
> causes the iterator block a few lines below to return partial matches.

That implies that there's something else corrupt in the index, because
the=20
presence key will never be the same size as an equality key.

>
> Thanks,
> Petteri
>
> -----Original Message-----
> From: openldap-bugs-bounces@OpenLDAP.org
> [mailto:openldap-bugs-bounces@OpenLDAP.org] On Behalf Of
> petteri.stenius@ubisecure.com
> Sent: Monday, October 25, 2010 1:35 PM
> To: openldap-its@openldap.org
> Subject: (ITS#6683) DDS fails with expired branches
>
> Full_Name:=3D20
> Version: 2.4.23
> OS: Linux
> URL: ftp://ftp.openldap.org/incoming/
> Submission from: (NULL) (195.197.205.34)
>
>
> Hello,
>
> I have a directory with branches of dynamicObject entries. It looks
like
> if the
> entryExpireTimestamp value is the same on objects within a branch then
> DDS
> search for expired objects will only find the top-most object. This
> results in
> remove failing with message
>
> DDS dn=3D3D"cn=3D3Dtop,cn=3D3Droot,dc=3D3Dtest" is non-leaf; =
deferring.
>
>
> To reproduce
>
> OpenLDAP 2.4.23, Berkeley DB 4.6.21
>
> Use slapadd to prepare directory with following
>
> dn: cn=3D3DRoot,dc=3D3Dtest
> objectClass: top
> objectClass: applicationProcess
> cn: Root
>
> dn: cn=3D3Dtop,cn=3D3DRoot,dc=3D3Dtest
> objectClass: top
> objectClass: device
> objectClass: dynamicObject
> entryTTL: 60
> entryExpireTimestamp: 20101024113626Z
> cn: top
>
> dn: cn=3D3Dleaf1,cn=3D3Dtop,cn=3D3DRoot,dc=3D3Dtest
> objectClass: top
> objectClass: device
> objectClass: dynamicObject
> entryTTL: 60
> entryExpireTimestamp: 20101024113626Z
> cn: leaf1
>
> dn: cn=3D3Dleaf2,cn=3D3Dtop,cn=3D3DRoot,dc=3D3Dtest
> objectClass: top
> objectClass: device
> objectClass: dynamicObject
> entryTTL: 60
> entryExpireTimestamp: 20101024113626Z
> cn: leaf2
>
> dn: cn=3D3Dleaf3,cn=3D3Dtop,cn=3D3DRoot,dc=3D3Dtest
> objectClass: top
> objectClass: device
> objectClass: dynamicObject
> entryTTL: 60
> entryExpireTimestamp: 20101024113626Z
> cn: leaf3
>
>
> Relevant slapd.conf entries
>
> database        bdb
> suffix          "cn=3D3DRoot,dc=3D3Dtest"
> rootdn          "cn=3D3DRoot,dc=3D3Dtest"
> rootpw          "password"
>
> overlay         dds
> dds-default-ttl 3600
> dds-min-ttl     60
> dds-interval    60
> dds-state       true
> index           entryExpireTimestamp eq,pres
>
> access to dn.subtree=3D3D"cn=3D3DRoot,dc=3D3Dtest"
>          by users write
>          by * read
>
>
> Running "slapd -d 1 -d 256" produces following
>
> put_filter:
>
"(&(objectClass=3D3DdynamicObject)(entryExpireTimestamp<=3D3D201010250824=
46Z
)=3D
> )"
> put_filter: AND
> put_filter_list
>
"(objectClass=3D3DdynamicObject)(entryExpireTimestamp<=3D3D20101025082446=
Z)"
> put_filter: "(objectClass=3D3DdynamicObject)"
> put_filter: simple
> put_simple_filter: "objectClass=3D3DdynamicObject"
> put_filter: "(entryExpireTimestamp<=3D3D20101025082446Z)"
> put_filter: simple
> put_simple_filter: "entryExpireTimestamp<=3D3D20101025082446Z"
> ber_scanf fmt ({mm}) ber:
> ber_scanf fmt ({mm}) ber:
> =3D3D>  

Message of length 7796 truncated

Up to top level
Build   Contrib   Development   Documentation   Historical   Incoming   Software Bugs   Software Enhancements   Web  

Logged in as guest


The OpenLDAP Issue Tracking System uses a hacked version of JitterBug

______________
© Copyright 2013, OpenLDAP Foundation, info@OpenLDAP.org