Comment déclencher Denial-of-Service Regex en PHP?

Question

Comment puis-je déclencher un Regex-DOS en utilisant la fonction preg_match() en utilisant une expression régulière malveillante (par exemple (a +) +)?

Par exemple, j'ai la situation suivante:

preg_match('/(a+)+/',$input); 

Si je contrôle sur $input, comment pourrais-je déclencher une attaque DOS ou atteindre le backtrack limite des preg_* fonctions en php?

Comment est-ce que je pourrais faire ceci avec les expressions suivantes?

([a-zA-Z]+)* 
(a|aa)+ 
(a|a?)+ 
(.*a){x} | for x > 10 

Answer 1

Il n'y a aucun moyen de déclencher ODER sur (a+)+, ([a-zA-Z]+)*, (a|aa)+, (a|a?)+, car il n'y a rien qui peut provoquer une défaillance du match et retours en arrière de déclenchement après la partie problématique du regex.

Si vous modifiez le regex un peu, par exemple, adding b$ after each of the regex above, vous pouvez déclencher retours en arrière catastrophique avec une entrée comme aaa ... aabaa ... aa. En fonction de la mise en œuvre et de l'optimisation du moteur, il existe des cas où nous attendons un retour en arrière catastrophique, mais le moteur ne montre aucun signe d'un tel comportement.

Par exemple, étant donné (a+)+b et l'entrée aaa ... aac, PCRE fails the match outright, car il a une optimisation qui vérifie le caractère requis dans la chaîne d'entrée avant de commencer la bonne correspondance. Sachant ce que le moteur fait, nous pouvons throw off its early detection avec l'entrée aaa ... aacb et obtenir le moteur pour montrer le retour en arrière catastrophique.

Quant à (.*a){x}, il est possible de déclencher ODER, car il a une condition à défaut de moins x itérations. Étant donné la chaîne d'entrée aaa ... a (avec x ou plus du caractère a), la regex continue d'essayer toutes les permutations de a à la fin de la chaîne car elle revient en arrière de la fin de la chaîne. Par conséquent, la complexité de la regex est O (2 ^x). Sachant cela, nous pouvons dire que l'effet est plus visible lorsque x est le plus grand nombre, let's say 20. En passant, c'est un cas rare où une chaîne correspondante a la complexité du pire cas.