Администрация платформы VirusTotal сообщила, что на этой неделе исправила ошибку, которая замедляла поиск угроз на сайте. Проблема затрагивала движок сканирования YARA, который является компонентом VirusTotal и позволяет исследователям осуществлять поиск по огромной базе малвари с помощью простых текстовых правил.
Разработчик, VirusTotal и создатель YARA Виктор Мануэль Альварес пишет в Twitter, что в корне этой проблемы лежал простой паттерн.
{ 00000008 [1-60] 00 [1-60] 00 [1-60] 00000008 [1-60] 00 [1-60] 00 [1-60] 00000008 [1-60] 00 [1-60] BB }
— Victor M. Alvarez (@plusvic) July 8, 2021
«Фактический паттерн был еще более незаметным, он выглядел похожим на другие паттерны, которые не создавали никаких проблем, но дьявол кроется в деталях. Причиной бага были множественные и относительно длинные переходы, такие как [0-60], разделенные коротким и распространенным паттерном 00.
YARA использует два разных алгоритма для сопоставления таких шаблонов: один — более сложный, для полноценных регулярных выражений, а другой — более простой и примитивный алгоритм для определенных hex-паттернов, подобных приведенному выше.
Такие HEX-паттерны могут сопоставляться с использованием полноценного алгоритма регулярных выражений (их можно представить как обычные regexp), но более примитивный алгоритм обычно быстрее. *Обычно*.
Полноценный алгоритм регулярных выражений медленнее, чем примитивный в 99% случаев, однако у него есть одно хорошее свойство: его временная сложность линейна, и нет “плохих случаев”, которые могут замедлить алгоритм экспоненциально.
Примитивный алгоритм в большинстве случаев быстрее, но он имеет экспоненциальный рост во времени. “Плохие случаи” действительно плохи. Правило, вызвавшее эту ошибку, один из таких по-настоящему плохих случаев», — рассказывает Альварес.
Эксперт отмечает, что описанная проблема – это встречающийся крайне редко сценарий, которого в компании не видели годами. Однако в итоге проблема коснулась клиентов VirusTotal, особенно 7 июля 2021 года, когда ошибка замедлила большинство поисков YARA на платформе.
Как теперь сообщают в VirusTotal, проблема полностью устранена, и платформа уже работает в нормальном режиме.
