From 39a822761b5388c78377ed0ddb2bebd8370859d4 Mon Sep 17 00:00:00 2001
From: Valery Kharseko <vharseko@3a-systems.ru>
Date: Thu, 11 Jun 2026 08:29:31 +0000
Subject: [PATCH] [#648] slow `DN.valueOf` / `AVA` normalization for nested DN-syntax values (#649)
---
opendj-core/src/test/java/org/forgerock/opendj/ldap/DNTestCase.java | 18 ++++++
opendj-core/src/test/java/org/forgerock/opendj/ldap/RDNTestCase.java | 40 +++++++++++++
opendj-core/src/main/java/org/forgerock/opendj/ldap/AVA.java | 21 +++++++
opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/DistinguishedNameEqualityMatchingRuleImpl.java | 44 ++++++++++++++
opendj-core/src/main/java/org/forgerock/opendj/ldap/RDN.java | 21 ++++++
opendj-core/src/main/resources/com/forgerock/opendj/ldap/core.properties | 4 +
opendj-core/src/test/java/org/forgerock/opendj/ldap/schema/DistinguishedNameEqualityMatchingRuleTest.java | 19 ++++++
7 files changed, 165 insertions(+), 2 deletions(-)
diff --git a/opendj-core/src/main/java/org/forgerock/opendj/ldap/AVA.java b/opendj-core/src/main/java/org/forgerock/opendj/ldap/AVA.java
index 285d013..14ddecb 100644
--- a/opendj-core/src/main/java/org/forgerock/opendj/ldap/AVA.java
+++ b/opendj-core/src/main/java/org/forgerock/opendj/ldap/AVA.java
@@ -13,6 +13,7 @@
*
* Copyright 2010 Sun Microsystems, Inc.
* Portions copyright 2011-2016 ForgeRock AS.
+ * Portions copyright 2021-2026 3A Systems, LLC
*/
package org.forgerock.opendj.ldap;
@@ -712,6 +713,26 @@
* <p>
* These bytes are reserved to represent respectively the RDN separator,
* the AVA separator and the escape byte in a normalized byte string.
+ * <p>
+ * NOTE (OpenDJ issue #648): the escaping is intentionally "self-nesting" and the
+ * repeated escaping across nesting levels is required, not redundant. The escaped
+ * output itself still contains reserved bytes (an escaped 0x00 becomes the pair
+ * 0x02 0x00), so when a DN-syntax attribute value is normalized - and its normalized
+ * value is itself the normalized byte string of a nested DN - the enclosing AVA must
+ * escape those reserved bytes again. This is mandatory to keep the flat normalized
+ * byte string both unambiguous (correct {@code equals}/{@code hashCode}) and
+ * byte-comparable (correct hierarchical {@code compareTo} ordering): the escape byte
+ * 0x02 sorts after the 0x00/0x01 separators, so structural separators always sort
+ * before escaped content.
+ * <p>
+ * The downside is that the number of reserved bytes roughly doubles per nesting level,
+ * so a value that recursively nests DN-syntax values N levels deep produces a
+ * normalized form of size ~2^N. This blow-up is inherent to any order-preserving,
+ * separator-escaped encoding that embeds itself, and it cannot be removed without
+ * breaking the ordering contract or the on-disk index key format. It is therefore
+ * mitigated by bounding the nesting depth and the normalized size in
+ * {@code DistinguishedNameEqualityMatchingRuleImpl} rather than by changing this
+ * encoding. Such deep self-nesting never occurs in legitimate data.
*/
private ByteString escapeBytes(final ByteString value) {
if (!needEscaping(value)) {
diff --git a/opendj-core/src/main/java/org/forgerock/opendj/ldap/RDN.java b/opendj-core/src/main/java/org/forgerock/opendj/ldap/RDN.java
index af69c2e..5e69345 100644
--- a/opendj-core/src/main/java/org/forgerock/opendj/ldap/RDN.java
+++ b/opendj-core/src/main/java/org/forgerock/opendj/ldap/RDN.java
@@ -13,6 +13,7 @@
*
* Copyright 2009-2010 Sun Microsystems, Inc.
* Portions copyright 2011-2016 ForgeRock AS.
+ * Portions copyright 2026 3A Systems, LLC
*/
package org.forgerock.opendj.ldap;
@@ -29,6 +30,7 @@
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
+import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.TreeSet;
@@ -71,6 +73,19 @@
public final class RDN implements Iterable<AVA>, Comparable<RDN> {
/**
+ * Comparator used to detect duplicate attribute types within a multi-valued RDN.
+ * It only compares the attribute types and, deliberately, does not normalize the
+ * attribute values (which can be very expensive for DN-syntax values).
+ */
+ private static final Comparator<AVA> ATTRIBUTE_TYPE_COMPARATOR =
+ new Comparator<AVA>() {
+ @Override
+ public int compare(final AVA o1, final AVA o2) {
+ return o1.getAttributeType().compareTo(o2.getAttributeType());
+ }
+ };
+
+ /**
* A constant holding a special RDN having zero AVAs
* and which sorts before any RDN other than itself.
*/
@@ -280,8 +295,12 @@
}
break;
default:
+ // Sort by attribute type only: detecting duplicate attribute types does not
+ // require normalizing the attribute values. Normalizing values here would be
+ // very expensive (and potentially pathological) for DN-syntax attribute values,
+ // which are themselves parsed recursively as DNs (see OpenDJ issue #648).
final AVA[] sortedAVAs = Arrays.copyOf(avas, avas.length);
- Arrays.sort(sortedAVAs);
+ Arrays.sort(sortedAVAs, ATTRIBUTE_TYPE_COMPARATOR);
AttributeType previousAttributeType = null;
for (AVA ava : sortedAVAs) {
if (ava.getAttributeType().equals(previousAttributeType)) {
diff --git a/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/DistinguishedNameEqualityMatchingRuleImpl.java b/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/DistinguishedNameEqualityMatchingRuleImpl.java
index 3bd5973..dc157fa 100644
--- a/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/DistinguishedNameEqualityMatchingRuleImpl.java
+++ b/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/DistinguishedNameEqualityMatchingRuleImpl.java
@@ -13,9 +13,11 @@
*
* Copyright 2009-2010 Sun Microsystems, Inc.
* Portions copyright 2011-2016 ForgeRock AS.
+ * Portions copyright 2024-2026 3A Systems, LLC
*/
package org.forgerock.opendj.ldap.schema;
+import static com.forgerock.opendj.ldap.CoreMessages.ERR_ATTR_SYNTAX_DN_MAX_DEPTH;
import static org.forgerock.opendj.ldap.schema.SchemaConstants.*;
import org.forgerock.i18n.LocalizedIllegalArgumentException;
@@ -30,6 +32,35 @@
*/
final class DistinguishedNameEqualityMatchingRuleImpl extends AbstractEqualityMatchingRuleImpl {
+ /**
+ * The maximum number of nested DN-syntax attribute values that will be normalized.
+ * <p>
+ * Normalizing a DN-syntax attribute value requires parsing the value as a DN and
+ * normalizing it, which in turn normalizes any nested DN-syntax attribute value, and
+ * so on recursively. This bounds that recursion to protect against stack overflow for
+ * maliciously or accidentally crafted values (see OpenDJ issue #648).
+ */
+ static final int MAX_NESTED_DN_DEPTH = 100;
+
+ /**
+ * The maximum size, in bytes, of a normalized DN-syntax attribute value.
+ * <p>
+ * Each nesting level escapes the reserved separator bytes of the level below, which
+ * roughly doubles the number of reserved bytes per level. A crafted value can therefore
+ * cause the normalized form to grow exponentially with the nesting depth (see OpenDJ
+ * issue #648). Values whose normalized form would exceed this limit are rejected so that
+ * the AVA falls back to a byte-wise comparison instead of consuming unbounded CPU/memory.
+ */
+ static final int MAX_NORMALIZED_VALUE_SIZE = 1 << 20;
+
+ /** Tracks the current DN-syntax value normalization recursion depth per thread. */
+ private static final ThreadLocal<int[]> CURRENT_DEPTH = new ThreadLocal<int[]>() {
+ @Override
+ protected int[] initialValue() {
+ return new int[1];
+ }
+ };
+
DistinguishedNameEqualityMatchingRuleImpl() {
super(EMR_DN_NAME);
}
@@ -37,11 +68,22 @@
@Override
public ByteString normalizeAttributeValue(final Schema schema, final ByteSequence value)
throws DecodeException {
+ final int[] depth = CURRENT_DEPTH.get();
+ if (depth[0] >= MAX_NESTED_DN_DEPTH) {
+ throw DecodeException.error(ERR_ATTR_SYNTAX_DN_MAX_DEPTH.get(value.toString(), MAX_NESTED_DN_DEPTH));
+ }
+ depth[0]++;
try {
DN dn = DN.valueOf(value.toString(), schema.asNonStrictSchema());
- return dn.toNormalizedByteString();
+ final ByteString normalized = dn.toNormalizedByteString();
+ if (normalized.length() > MAX_NORMALIZED_VALUE_SIZE) {
+ throw DecodeException.error(ERR_ATTR_SYNTAX_DN_MAX_DEPTH.get(value.toString(), MAX_NESTED_DN_DEPTH));
+ }
+ return normalized;
} catch (final LocalizedIllegalArgumentException e) {
throw DecodeException.error(e.getMessageObject());
+ } finally {
+ depth[0]--;
}
}
diff --git a/opendj-core/src/main/resources/com/forgerock/opendj/ldap/core.properties b/opendj-core/src/main/resources/com/forgerock/opendj/ldap/core.properties
index a7b9847..a73a842 100644
--- a/opendj-core/src/main/resources/com/forgerock/opendj/ldap/core.properties
+++ b/opendj-core/src/main/resources/com/forgerock/opendj/ldap/core.properties
@@ -14,6 +14,7 @@
# Copyright 2010 Sun Microsystems, Inc.
# Portions copyright 2011-2016 ForgeRock AS.
# Portions Copyright 2014 Manuel Gaupp
+# Portions Copyright 2024-2026 3A Systems, LLC
ERR_ATTR_SYNTAX_UNKNOWN_APPROXIMATE_MATCHING_RULE=Unable to retrieve \
approximate matching rule %s used as the default for the %s attribute syntax. \
@@ -108,6 +109,9 @@
could not be parsed as a valid distinguished name because one of the RDN \
components included a value with an escaped hexadecimal digit that was not \
followed by a second hexadecimal digit
+ERR_ATTR_SYNTAX_DN_MAX_DEPTH=The provided value "%s" could not be parsed as a \
+ valid distinguished name because it contains more than %d levels of nested \
+ distinguished name (DN-syntax) attribute values
WARN_ATTR_SYNTAX_INTEGER_INITIAL_ZERO=The provided value "%s" could \
not be parsed as a valid integer because the first digit may not be zero \
unless it is the only digit
diff --git a/opendj-core/src/test/java/org/forgerock/opendj/ldap/DNTestCase.java b/opendj-core/src/test/java/org/forgerock/opendj/ldap/DNTestCase.java
index 9f1ebd0..d9960e7 100644
--- a/opendj-core/src/test/java/org/forgerock/opendj/ldap/DNTestCase.java
+++ b/opendj-core/src/test/java/org/forgerock/opendj/ldap/DNTestCase.java
@@ -13,6 +13,7 @@
*
* Copyright 2010 Sun Microsystems, Inc.
* Portions copyright 2011-2016 ForgeRock AS.
+ * Portions copyright 2021-2026 3A Systems, LLC
*/
package org.forgerock.opendj.ldap;
@@ -675,6 +676,23 @@
}
/**
+ * Reproduces OpenDJ issue #648: parsing a DN whose multi-valued RDN contains duplicate
+ * DN-syntax attribute types (here 2.5.4.1, aliasedObjectName) with deeply nested values
+ * used to take minutes because the duplicate-type detection normalized the values. It
+ * must now fail fast with a "duplicate AVA types" error.
+ */
+ @Test(timeOut = 30000, expectedExceptions = LocalizedIllegalArgumentException.class)
+ public void testValueOfWithDuplicateNestedDnSyntaxAvasIsFast() throws Exception {
+ final StringBuilder nested = new StringBuilder();
+ for (int i = 0; i < 30; i++) {
+ nested.append("2.5.4.1=");
+ }
+ nested.append("0=0oa");
+ final String dnString = "NTLou= r1oa +2.5.4.1=" + nested + " +2.5.4.1=2.";
+ DN.valueOf(dnString);
+ }
+
+ /**
* Test the isChildOf method.
*
* @param s
diff --git a/opendj-core/src/test/java/org/forgerock/opendj/ldap/RDNTestCase.java b/opendj-core/src/test/java/org/forgerock/opendj/ldap/RDNTestCase.java
index a6d6547..f66ba78 100644
--- a/opendj-core/src/test/java/org/forgerock/opendj/ldap/RDNTestCase.java
+++ b/opendj-core/src/test/java/org/forgerock/opendj/ldap/RDNTestCase.java
@@ -13,6 +13,7 @@
*
* Copyright 2010 Sun Microsystems, Inc.
* Portions copyright 2011-2016 ForgeRock AS.
+ * Portions copyright 2026 3A Systems, LLC
*/
package org.forgerock.opendj.ldap;
@@ -312,6 +313,45 @@
}
/**
+ * Detecting duplicate attribute types in a multi-valued RDN must only compare the
+ * attribute types and must not normalize the attribute values. Normalizing DN-syntax
+ * values (such as {@code aliasedObjectName}, OID 2.5.4.1) is potentially very expensive
+ * and used to make this validation pathologically slow (OpenDJ issue #648).
+ */
+ @Test(timeOut = 30000, expectedExceptions = LocalizedIllegalArgumentException.class)
+ public void testDuplicateDnSyntaxAvasAreDetectedQuickly() {
+ final StringBuilder nested = new StringBuilder();
+ for (int i = 0; i < 30; i++) {
+ nested.append("2.5.4.1=");
+ }
+ nested.append("0=0oa");
+ // Three AVAs sharing the same DN-syntax attribute type (2.5.4.1) so the default
+ // (3+) validation branch is exercised. Validation must throw without normalizing.
+ final AVA a1 = new AVA("2.5.4.1", nested.toString());
+ final AVA a2 = new AVA("2.5.4.1", nested.toString());
+ final AVA a3 = new AVA("2.5.4.1", "value");
+ new RDN(a1, a2, a3);
+ }
+
+ /**
+ * A multi-valued RDN built from distinct DN-syntax attribute types must be created
+ * quickly: the duplicate-type detection must not normalize the (expensive) values.
+ */
+ @Test(timeOut = 30000)
+ public void testDistinctDnSyntaxAvasAreValidatedQuickly() {
+ final StringBuilder nested = new StringBuilder();
+ for (int i = 0; i < 30; i++) {
+ nested.append("2.5.4.1=");
+ }
+ nested.append("0=0oa");
+ final AVA a1 = new AVA("2.5.4.1", nested.toString());
+ final AVA a2 = new AVA("2.5.4.34", nested.toString());
+ final AVA a3 = new AVA("cn", "value");
+ final RDN rdn = new RDN(a1, a2, a3);
+ assertEquals(rdn.size(), 3);
+ }
+
+ /**
* Test RDN string decoder against illegal strings.
*
* @param rawRDN
diff --git a/opendj-core/src/test/java/org/forgerock/opendj/ldap/schema/DistinguishedNameEqualityMatchingRuleTest.java b/opendj-core/src/test/java/org/forgerock/opendj/ldap/schema/DistinguishedNameEqualityMatchingRuleTest.java
index 5a5a79e..c9f0228 100644
--- a/opendj-core/src/test/java/org/forgerock/opendj/ldap/schema/DistinguishedNameEqualityMatchingRuleTest.java
+++ b/opendj-core/src/test/java/org/forgerock/opendj/ldap/schema/DistinguishedNameEqualityMatchingRuleTest.java
@@ -13,6 +13,7 @@
*
* Copyright 2009-2010 Sun Microsystems, Inc.
* Portions copyright 2013-2016 ForgeRock AS.
+ * Portions copyright 2024-2026 3A Systems, LLC
*/
package org.forgerock.opendj.ldap.schema;
@@ -205,4 +206,22 @@
}
return new ByteStringBuilder().appendByte(0).appendUtf8(s).toByteString();
}
+
+ /**
+ * Reproduces OpenDJ issue #648: normalizing a DN-syntax value that recursively nests many
+ * DN-syntax values used to take minutes (and exhaust memory) because each nesting level
+ * roughly doubles the size of the normalized form. Normalization must now be bounded and
+ * complete in a reasonable time.
+ */
+ @Test(timeOut = 30000)
+ public void testNormalizationOfDeeplyNestedDnValueIsBounded() throws Exception {
+ final StringBuilder nested = new StringBuilder("2.5.4.1=");
+ for (int i = 0; i < 60; i++) {
+ nested.append("2.5.4.1=");
+ }
+ nested.append("0=0oa");
+ final ByteString normalized =
+ getRule().normalizeAttributeValue(ByteString.valueOfUtf8(nested.toString()));
+ assertThat(normalized).isNotNull();
+ }
}
--
Gitblit v1.10.0