VirusTotal fixes bug that slowed down threat hunting operations

Malware scanning service and threat intelligence platform VirusTotal said it fixed a bug today that was slowing down threat hunting operations on its website.

The bug impacted the YARA scanning engine, a component of the VirusTotal website that allows security researchers to use text-based rules to search through the site's gigantic malware database.

According to Victor Manuel Alvarez, a software engineer at VirusTotal and the creator of the YARA threat-hunting engine, an innocent-looking pattern was to blame for this week's problems.

{ 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

In a Twitter thread, Alvarez described the problem as follows:

"The actual pattern was even more inconspicuous, it looked very similar to other patterns that don't cause any trouble, but the devil is in the details. The multiple and relatively long jumps like [0-60], separated by the short and common pattern 00 were the cause of the issue.

YARA uses two different algorithms for matching patterns like this: one is a more complex algorithm for full-fledged regular expressions, and the other is a simpler, more naive algorithm for certain hex patterns like the one above.

These hex patterns could be matched using the full-fledged regexp algorithm (they can be expressed as a tradicional regexp) but the naive algorithm is usually faster. *Usually*.

The full-fledged regexp algorithm is slower than the naive algorithm for 99% of the cases, but it has a good property: it's time complexity is linear, there are no "bad cases" that can slow down the algorithm exponentially.

The naive algorithm is faster in most cases, but it's has an exponential time grow. Bad cases are really bad. The rule that caused this issue is one of those really bad cases."

Alvarez described the issue as a very rare scenario and one that the company had not seen in years.

The issue impacted VirusTotal customers, especially on Wednesday, when it slowed down most YARA rule searches on the platform.

"It impacted our research into the Kaseya incident, but since this is the first issue we've seen on VirusTotal, our frustration level remained low," a researcher working with CERT France told The Record.

The issue has been fixed, and the VirusTotal service is back up and running normally today, a VT engineer told us.

Read this if you want to know why VT was having problems yesterday. Full of nifty details! https://t.co/vu8n6Wou3b

— Wesley Shields (@wxs) July 8, 2021