[#648] slow `DN.valueOf` / `AVA` normalization for nested DN-syntax values ...

Valery Kharseko

4 days ago 39a822761b5388c78377ed0ddb2bebd8370859d4

 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)) {

 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)) {

 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]--;
        }
    }


 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

 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

 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

 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();
    }
}