«Фактический паттерн был еще более незаметным, он выглядел похожим на другие паттерны, которые не создавали никаких проблем, но дьявол кроется в деталях. Причиной бага были множественные и относительно длинные переходы, такие как [0-60], разделенные коротким и распространенным паттерном 00.
YARA использует два разных алгоритма для сопоставления таких шаблонов: один — более сложный, для полноценных регулярных выражений, а другой — более простой и примитивный алгоритм для определенных hex-паттернов, подобных приведенному выше.
Такие HEX-паттерны могут сопоставляться с использованием полноценного алгоритма регулярных выражений (их можно представить как обычные regexp), но более примитивный алгоритм обычно быстрее. *Обычно*.
Полноценный алгоритм регулярных выражений медленнее, чем примитивный в 99% случаев, однако у него есть одно хорошее свойство: его временная сложность линейна, и нет “плохих случаев”, которые могут замедлить алгоритм экспоненциально.
Примитивный алгоритм в большинстве случаев быстрее, но он имеет экспоненциальный рост во времени. “Плохие случаи” действительно плохи. Правило, вызвавшее эту ошибку, один из таких по-настоящему плохих случаев», — рассказывает Альварес.