Discussions around boreal and YARA-X

[vthib]

@vthib, by following a link in YARA's repository I landed here and discovered this project. I don't know if you have seen https://github.com/VirusTotal/yara-x, but the goals are very similar: a complete implementation of YARA in Rust, that solves some of the pain points experienced by YARA users (like slow rules that should be actually fast) and developers (like the parser tightly coupled with YARA itself that disallows its reuse).

The approach however is different. YARA-X converts rule conditions into WebAssembly code, that in turns gets translated into native code. This makes conditions that rely heavily on loops much faster. The goal is that condition evaluation is 10x faster than the existing YARA on average. I see that you seem to have experience in Rust (more than myself, I'm gradually learning Rust with the YARA-X project), so if you would like to contribute to YARA-X in some way you are really welcomed. The project is still immature and unstable, but I've made a lot of progress already, and have implemented most of the condition evaluation logic.

Originally posted by @plusvic in #6 (comment)

[vthib]

Hi @plusvic, and thanks for the comment! I took the liberty of moving the discussion here,
so as not to pester you with notifications on the many pushes I'll probably do on #6 :)

I did know about YARA-X yes, and seen you talk about Rust on twitter as well, but I hadn't look into it too much.
From the description I thought it was mainly a linter, and did not know about the condition's compilation stuff, that's quite interesting! I'll definitely try to look into it a bit more.

For boreal, the only really missing part is performance improvements.
There are still significant improvements that can be found from improving atoms extractions and string scanning (where YARA does some great stuff).
However, time spent evaluating rules after the scanning always seemed negligible in all the profiling I did. Maybe I need to dig more, but I hadn't had the impression that improving how conditions are evaluated would help gain significant overall time.
Hence the quite naive (but good enough for now) recursive evaluation on a AST tree built for the conditions.

Was the condition evaluation a big factor in the end in YARA? I might need to revisit this, but there's a lot of big gains to get in the string scanning implem with many open questions to answer. Do you know how you plan to implement this string scanning in YARA-X?

[plusvic]

Regarding, the weight of condition evaluation in overall performance, it depends a lot on the rules. In the vast majority of rules the scanning phase out-weights the condition evaluation by a large factor, but in with certain rules that depend heavily on loops (even nested loops) the condition evaluation becomes the bottleneck. In VirusTotal we had this problem many times, and even had to forbid rules with loops like for any i in (0..filesize) : (...), which was a common construct. With a 100MB files this loop can iterate 100 million times. When you carefully curate your rules that's probably not an issue, but that's certainly a problem for us in VirusTotal.

Regarding the plans for implementing string scanning in YARA-X.. the first important goal is fixing the issue that you solved with boreal too, not scanning the file if not strictly required. The idea is start evaluating the condition first, and triggering the scanning phase lazily, when the condition needs to know if some pattern is present or not. At that moment it looks for all the patterns at the same time as in the current implementation.

I plan to use the same technique for string scanning, atom extraction + aho-corasick. But I want to introduce a few improvements, like eliminating duplicated patterns (something that also helps in our VirusTotal use case, as we have a lot duplicated patterns). I explored the possibility of using https://github.com/intel/hyperscan, but has some major drawbacks that make it unsuitable for YARA's needs.

Some other goals for YARA-X:

• A more user-friendly and flexible CLI application, with improvements like JSON output.
• A code formatting tool integrated in the CLI application, like rustfmt and gofmt.
• Better error reporting. (rustc-style, as you also did with boreal)
• More efficient modules. In the sense that the current YARA implementation does a lot of work with every file scan just for defining constant fields.
• Modules based in protobuf format. With this you should be able to implement a module just be writing a .proto file for it and filling the protobuf with information extracted from the file. This also opens the door for feeding structured data into YARA from other languages.

In this discussion there are many other ideas for the long term:
VirusTotal/yara#1781

If you want to collaborate with YARA-X let me know, there are a few areas in which we could find ways for working in parallel. Also, an overall review of the code would be great, I'm new to Rust, this is my first project with the language and I would like to hear about other ways of doing things.

And finally, and out of curiosity, what moved you to start the boreal project? It is a side project for learning Rust? Do you plan to use it as part of a larger project?

[plusvic]

I've being looking around and found this comment in the README file:

Using mmap/MapViewOfFile to avoid duplicating the scanned file in memory.
This is unfortunately not done because of the trickiness of doing this properly in Rust, as reading of a file mapping can trigger signals (SIGBUS) or exceptions. I hope to have a solution for this in the future.

I'm curious about this because I'm using https://crates.io/crates/memmap for mapping the file to be scanned. Under which circumstances you have found SIGBUS signals while reading from mem-mapped files?

Also, thanks to boreal I've discovered that https://github.com/BurntSushi/aho-corasick is really fast. I knew about that crate, but didn't imagine that it was so fast.

[vthib]

Thanks for the explanation, I can see how rules using for i in 0..filesize would cause huge performance issues. I probably only tested with well written/curated rules, although I did try to test with some less clean rules as well, just never had rules this problematic.

I also had a look at hyperscan as I originally intended to try it, and I ended up dropping as well although I don't remember exactly the details :D It could be interesting to revisit this, it shouldn't be too hard to try and use it in boreal.

It definitely looks like we share a lot of goals with our projects! I spent quite some time trying to find a design for slimmer modules, and originally went with one design that I dropped. I currently have a half working solution, but have some ideas on how it could be improved. It could definitely be interesting to share ideas on this. I also share almost all of the other goals you mentioned.

I guess the main goal difference of the two projects is in compatibility with existing rules. I designed mine for full compatibility with YARA, even to a fault, so that it can be used in place of it with full confidence that it would work. I feel that this is needed to help people make the change, but it also brings all the existing issues of YARA into the project.

From what I can tell, you plan to make YARA-X an evolution of YARA, that would remove some syntax or reject some rules, in order to improve it? It definitely makes sense after so much time working on YARA.

Thanks for the link to VirusTotal/yara#1781, I did not know about it, there are a lot of great ideas in it.

As for my motivations, I wanted to do a well-sized non trivial personal Rust project for some time, and YARA (which i used at work) seemed like a great project to rewrite. Non trivial parsing, widely used which gives a lot of testing opportunities, opportunities to improve performances, and a quite open subject to experiment on (how to scan for all the strings & evaluate all the rules as fast as possible). There is no plan to use it in larger projects on my end, it is a personal project, although my goal is to see it used by other people.

I'll look into the YARA-X code in more details. It is a bit of a shame we ended up starting the two projects in parallel, given we have most of the same goals. Maybe there are opportunities to share efforts.

Finally, about the mmap paragraph. There are a lot of issues in using mmap in Rust, BurntSushi mentions some here https://users.rust-lang.org/t/how-unsafe-is-mmap/19635/5 (the whole thread is interesting). This is the reason the Mmap::new method you call is unsafe, which is indicated in its safety comment: https://docs.rs/memmap2/latest/memmap2/struct.Mmap.html#safety
An easy way to reproduce is to have a program mmap a file, and read from it in a loop. Then, truncate the file, and the program will end on a SIGBUS signal.

[plusvic]

If I recall right, the main issue I found with Hyperscan was that it is designed for returning the ending offset of each match. It has an option for returning the left-most possible offset where the match starts, but you won't get all the possible offsets where a matching pattern starts, and that's essential for supporting $a at X operations.

Regarding backward compatibility, I didn't mention it, but that's also a goal for YARA-X. Without backward compatibility it would be very hard for users to adopt YARA-X, so my plan is achieving 99% backward compatibility with existing rules (API compatibility is not a goal, and the CLI won't be a drop-in replacement for the existing one). I won't pursue 100% compatibility, which means that certain rules can fail to compile in YARA-X or work differently, but only on extreme cases where existing rules are actually wrong or rely on implementation details. For example, in this thread we are talking about a case where the user was using for 10 of ($b*) : (#) as #b1 + #b2 + #b.. > 10, which happens to work in YARA because of the way for loops were implemented. In YARA-X for 10 of ($b*) : (#) will behave exactly as for 10 of ($b*) : ($), which is the expected semantics. Another example is @a[-1], which is valid in YARA, but will raise an error in YARA-X because it doesn't make sense to use a negative index like that. The goal is that most of the existing rules will work as expected and only in a few, well-documented cases YARA-X will differ from YARA.

About mmap... the curious thing is that yesterday I did some tests by modifying boreal to use mmap instead of reading the whole file, and contrary to my expectations, reading the whole file was noticeable faster than using mmap. My test consisted in scanning a whole directory containing a mix of small and relatively large files, with a very simple rule that looked for a plain string. That was using MacOS, the results may differ in other OSes, but I still need to investigate the reason for those results. I was expecting at least the same performance in both cases.