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}