001/*
002    Licensed to the Apache Software Foundation (ASF) under one
003    or more contributor license agreements.  See the NOTICE file
004    distributed with this work for additional information
005    regarding copyright ownership.  The ASF licenses this file
006    to you under the Apache License, Version 2.0 (the
007    "License"); you may not use this file except in compliance
008    with the License.  You may obtain a copy of the License at
009
010       http://www.apache.org/licenses/LICENSE-2.0
011
012    Unless required by applicable law or agreed to in writing,
013    software distributed under the License is distributed on an
014    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015    KIND, either express or implied.  See the License for the
016    specific language governing permissions and limitations
017    under the License.
018 */
019package org.apache.wiki.util;
020
021import org.apache.logging.log4j.LogManager;
022import org.apache.logging.log4j.Logger;
023
024import java.util.regex.Matcher;
025import java.util.regex.Pattern;
026
027/**
028 * Evaluates {@link java.util.regex} matches with an upper bound on matching
029 * time. The JDK regex engine backtracks, so a pathological pattern such as
030 * {@code (a+)+$} matched against a long non-matching subject takes exponential
031 * time and pins a CPU ("catastrophic backtracking" / ReDoS). When either the
032 * pattern or the subject is user-controlled — as with wiki plugin parameters
033 * matched against page content — every match must be time-boxed.
034 * <p>
035 * The subject is wrapped in a deadline-checking {@link CharSequence}: the
036 * engine reads the subject on every matching step, so a runaway match is
037 * aborted shortly after the deadline passes and reported as a non-match.
038 *
039 * @since 3.0.1
040 */
041public final class TimeLimitedRegex {
042
043    private static final Logger LOG = LogManager.getLogger(TimeLimitedRegex.class);
044
045    /**
046     * Default time budget for a single match, in milliseconds. Value is
047     * <tt>{@value}</tt>.
048     */
049    public static final long DEFAULT_TIMEOUT_MILLIS = 1_000L;
050
051    /**
052     * The deadline is re-checked every this many character accesses; must be a
053     * power of two.
054     */
055    private static final int CHECK_MASK = 1_024 - 1;
056
057    private TimeLimitedRegex() {
058    }
059
060    /**
061     * Attempts to match the whole subject against the given pattern, giving up
062     * after {@link #DEFAULT_TIMEOUT_MILLIS} milliseconds.
063     *
064     * @param subject the character sequence to match.
065     * @param pattern the compiled pattern.
066     * @return {@code true} if the whole subject matches; {@code false} if it
067     * doesn't, or if the time budget was exceeded.
068     */
069    public static boolean matches(final CharSequence subject, final Pattern pattern) {
070        return matches(subject, pattern, DEFAULT_TIMEOUT_MILLIS);
071    }
072
073    /**
074     * Attempts to match the whole subject against the given pattern, giving up
075     * after {@code timeoutMillis} milliseconds. A match that exceeds its budget
076     * is logged as a warning and treated as a non-match.
077     *
078     * @param subject the character sequence to match.
079     * @param pattern the compiled pattern.
080     * @param timeoutMillis time budget for this match, in milliseconds.
081     * @return {@code true} if the whole subject matches; {@code false} if it
082     * doesn't, or if the time budget was exceeded.
083     */
084    public static boolean matches(final CharSequence subject, final Pattern pattern, final long timeoutMillis) {
085        final Matcher matcher = pattern.matcher(new DeadlineCharSequence(subject, System.nanoTime() + timeoutMillis * 1_000_000L));
086        try {
087            return matcher.matches();
088        } catch (final MatchTimeoutException e) {
089            LOG.warn("Regular expression '{}' exceeded its {} ms matching budget on a {} character subject; treating as no match",
090                    pattern.pattern(), timeoutMillis, subject.length());
091            return false;
092        }
093    }
094
095    /**
096     * Thrown internally when the matching deadline has passed.
097     */
098    private static final class MatchTimeoutException extends RuntimeException {
099
100        private static final long serialVersionUID = 1L;
101    }
102
103    /**
104     * View over a subject that aborts any regex match still reading it after
105     * the deadline.
106     */
107    private static final class DeadlineCharSequence implements CharSequence {
108
109        private final CharSequence m_subject;
110        private final long m_deadlineNanos;
111        private int m_accesses;
112
113        DeadlineCharSequence(final CharSequence subject, final long deadlineNanos) {
114            m_subject = subject;
115            m_deadlineNanos = deadlineNanos;
116        }
117
118        @Override
119        public char charAt(final int index) {
120            if ((++m_accesses & CHECK_MASK) == 0 && System.nanoTime() - m_deadlineNanos > 0) {
121                throw new MatchTimeoutException();
122            }
123            return m_subject.charAt(index);
124        }
125
126        @Override
127        public int length() {
128            return m_subject.length();
129        }
130
131        @Override
132        public CharSequence subSequence(final int start, final int end) {
133            return new DeadlineCharSequence(m_subject.subSequence(start, end), m_deadlineNanos);
134        }
135
136        @Override
137        public String toString() {
138            return m_subject.toString();
139        }
140
141    }
142}