Optimize memory usage when scanning processes and files

[plusvic]

From zeroStei...@gmail.com on December 20, 2011 19:01:35

This is a feature request not a bug.

It would be helpful if Yara would not load entire files into memory to scan them but step through them with an sizeable overlap to avoid false negatives. It would also be very helpful if Yara would use a similar chunking method to scan processes because files can at least be scanned in as chunks of data by the controlling process.

Basically Yara's memory usage needs to have some limitation.

Original issue: http://code.google.com/p/yara-project/issues/detail?id=33

[plusvic]

From plus...@gmail.com on December 22, 2011 02:06:05

YARA uses memory-mapped files. If the scanned file is big your virtual memory usage will grow a lot, but that doesn't means that your physical memory usage should be the same, that depends on the available RAM and file size, the operating system will do it's magic to remove from physical memory the portions of the file that are not in use.

Process scanning is done in chunks, however the chunks can be big if the target process have big blocks of contiguous memory allocated. I think there is some room for improvement here.

[kallanreed]

I want to try a fix for process memory reading. Basically adding a new SectionReader type to keep track of the process handle, the buffer and the last read location of the section. Instead of allocating enough chunks for the whole section, one chunk would be reused.

The caller would call OpenReader to get a new reader and call a ReadNext function with the SectionReader which would either read the next chunk of the section or would return null or a failure code if the section is no longer readable. A HasMore flag would indicate that reading is incomplete and could be used in the caller's while condition.

When the caller is done reading the section, it would have to call a CloseReader which would free the internal buffer and detach from the process.

The benefit would be much smaller memory footprint during process scanning at the expense of potential memory consistency.

I need this behavior because the current memory characteristics will not work for the environment we want to use YARA in.

[jhumble]

YARA does seem to be using memory mapped files for OSX and Linux, but the Windows implementation using ReadProcessMemory, does result in a a huge increase in physical memory usage if I'm not mistaken.

Good luck, Kallenreed. This would be hugely helpful for me as well. I had started coding a POC implementation similar to what you've described for Windows.

So far, my solution was to no longer read data into each block in yr_process_get_memory and instead just stuff the process handle into the data field in the block structure. Then, when iterating over blocks in yr_rules_scan_mem_blocks I can call ReadProcessMemory to load the data for that one block, scan it, release it, and move onto the next block.

Your implementation using a SectionReader is much cleaner though, let me know if there is any way I can help!

[kallanreed]

Yeah, you don't really want to leak the platform specific code into the rules handler. I'll give my design a try this weekend and see if I can make it work for all three platforms. I don't have a Linux build machine handy so I'll need some help testing once I get a PR ready.

Sent from my iPhone

On Feb 18, 2016, at 14:48, Jeremy Humble <notifications@github.commailto:notifications@github.com> wrote:

YARA does seem to be using memory mapped files for OSX and Linux, but the Windows implementation using ReadProcessMemory, does result in a a huge increase in physical memory usage if I'm not mistaken.

Good luck, Kallenreed. This would be hugely helpful for me as well. I had started coding a POC implementation similar to what you've described for Windows.

So far, my solution was to no longer read data into each block in yr_process_get_memory and instead just stuff the process handle into the data field in the block structure. Then, when iterating over blocks in yr_rules_scan_mem_blocks I can call ReadProcessMemory to load the data for that one block, scan it, release it, and move onto the next block.

Your implementation using a SectionReader is much cleaner though, let me know if there is any way I can help!

Reply to this email directly or view it on GitHubhttps://github.com/plusvic/yara/issues/33#issuecomment-185966469.

[kallanreed]

I have a POC that I'd like some feedback on. The gist is that the section maps are loaded all at once and then sections are read and processed one at a time. I scanned notepad on Windows and the memory usage went from 90MB to 3MB.

Section Reader POC

It's currently only implemented for Windows but I think the pattern will work for BSD/Linux. Error handling isn't all there and the code's not cleaned up, but you can get a sense for where it's going.

Concerns

• Need to keep a context object between calls to yr_rules_scan_mem_blocks.
• It looks like Linux and BSD would also benefit from this (I do see yr_malloc for sections in both) but I'm not familiar enough with the platforms to be sure.
• I didn't see any place that expected all block to be available (the linked list) on the Context type in the case of a process memory scan. I'm not sure if any modules do.
• I don't know if I like returning an error code on section read completion but I don't like a null check.

@plusvic I'd like to know if I should continue down this path and finish this up.

[plusvic]

This solution is not correct, you are calling yr_rules_scan_mem_blocks
multiple times, once for each section. This means that each section is
handled as a separate file, with their own set of matches. If you scan a
process with this rule:

rule test {
strings:
$a = "foo"
$b = "bar"
condition:
$a and $b
}

...and the strings "foo" and "bar" appear in different sections within the
process address space, this rule won't match. That's not the expected
behavior.

I think the way to go is replacing the loop in yr_rules_scan_mem_blocks
from this:

while (block != NULL)
{
.
.

  block = block->next;

}

to this:

block = _yr_get_first_block(...)

while (block != NULL)
{
.
.

  block = _yr_get_next_block(...)

}

Instead of passing a linked list containing all the blocks to
yr_rules_scan_mem_blocks, you would pass a callback function responsible of
returning one block at a time. _yr_get_first_block() and _yr_get_next_block
would call the callback to get the blocks. This way
yr_rules_scan_mem_blocks don't need to know about how the blocks are
retrieved, they could be in a linked list built beforehand or they could be
read on demand. yr_rules_scan_proc would calling yr_rules_scan_mem_blocks
passing the appropriate callback for reading blocks from the process
address space.

On Sun, Feb 21, 2016 at 8:41 AM, Kyle Reed notifications@github.com wrote:

I have a POC that I'd like some feedback on. The gist is that the section
maps are loaded all at once and then sections are read and processed one at
a time. I scanned notepad on Windows and the memory usage went from 90MB to
3MB.

Section Reader POC
kallanreed@afc866e

It's currently only implemented for Windows but I think the pattern will
work for BSD/Linux. Error handling isn't all there and the code's not
cleaned up, but you can get a sense for where it's going.

Concerns

• Need to keep a context object between calls to
  yr_rules_scan_mem_blocks.
• It looks like Linux and BSD would also benefit from this (I do see
  yr_malloc for sections in both) but I'm not familiar enough with the
  platforms to be sure.
• I didn't see any place that expected all block to be available (the
  linked list) on the Context type in the case of a process memory scan. I'm
  not sure if any modules do.
• I don't know if I like returning an error code on section read
  completion but I don't like a null check.

@plusvic https://github.com/plusvic I'd like to know if I should
continue down this path and finish this up.

—
Reply to this email directly or view it on GitHub
https://github.com/plusvic/yara/issues/33#issuecomment-186769042.

[kallanreed]

I did point out the context problem in my comment above.

Need to keep a context object between calls to yr_rules_scan_mem_blocks.

My initial thought was to move the context into yr_rules_scan_procs and the have a _yr_scan_mem_blocks overload that accepted a context. The only reason I liked this was because I considered it less touch.

The block callback is a reasonable approach but it will require updating more callers. I'll see what the code looks like.

I did have another question re: BSD/Linux. It looks like it does allocate when reading process memory but some of the comments above seemed to indicate otherwise. Is this change needed on those platforms as well?

[kallanreed]

POC with a block iterator concept

@plusvic This is basically the callback implementation - I added a new type BLOCK_READER that tracks the advancement of the pointer in the buffer linked list. This way the section reader and the block reader behave basically the same way from the caller perspective. Also, it needed to return errors so the callback sets the block through an out param. I wasn't really thrilled about the void* in the callback but I don't know any other polymorphic idioms in C.

Anyway, the basic concepts are all there - should I spend the time to finish it? Any major concerns about the design or names?

[plusvic]

This is getting better, but still I have a few things to point out. Why not
simplifying everything and removing the section reader? I mean, we only
need one abstraction, the block reader. When scanning a process the block
reader simply fetches chunks of memory from the address space of the
process. Suppose yr_rules_scan_mem_blocks looks like this:

YR_API int yr_rules_scan_mem_blocks(
YR_RULES* rules,
YR_BLOCK_ITERATOR* iterator,
int flags,
YR_CALLBACK_FUNC callback,
void* user_data,
int timeout)

And YR_BLOCK_ITERATOR looks like this:

typedef _YR_BLOCK_ITERATOR {

void* context;

YR_MEMORY_BLOCK* first(typedef _YR_BLOCK_ITERATOR* _self); //
This is just a simplification, not actual valid C code. This should be
a pointer to a function.

YR_MEMORY_BLOCK* next(typedef _YR_BLOCK_ITERATOR* _self); //
This is just a simplification, not actual valid C code. This should be
a pointer to a function.

} YR_BLOCK_ITERATOR;

yr_rules_scan_mem_blocks receives a pointer to a structure
encapsulating a block iterator. The iterator structure contains a
pointer to the required context information and to functions "first"
and "next" to retrieve the first and next blocks. "first" and "next"
receive and pointer to the iterator itself in order to be able to
access the context information. This is just like a emulating a C++
class in pure C.

In yr_rules_scan_mem_blocks you just do:

block = iterator->first(iterator);

while (block != NULL)

{

....

block = iterator->next(iterator);

}

While scanning a process you simply create a new iterator with a pair
of "first" and "next" functions that reads from the address space of
the process. Each block corresponds to a section.

It would be very useful to provide a way of iterating over the blocks
without having to bring the actual chunk of data from the other
process. For example:

block = iterator->first(iterator);

while (block != NULL)

{

void* block_data = iterator->fetch_block(iterator, block);

....

block = iterator->next(iterator);

}

Here YR_MEMORY_BLOCK doesn't contain a pointer to the data, you retrieve
the block's data by calling another function doing the actual reading. This
way you decouple the block list iteration from the actual data reading.
This is useful in modules that iterate the blocks looking for a certain
address range, but don't need to bring in all the memory, just the range
they want.

On Mon, Feb 22, 2016 at 6:38 AM, Kyle Reed notifications@github.com wrote:

POC with a block iterator concept
kallanreed@f411ef0

@plusvic https://github.com/plusvic This is basically the callback
implementation - I added a new type BLOCK_READER that tracks the
advancement of the pointer in the buffer linked list. This way the section
reader and the block reader behave basically the same way from the caller
perspective. Also, it needed to return errors so the callback sets the
block through an out param. I wasn't really thrilled about the void* in the
callback but I don't know any other polymorphic idioms in C.

Anyway, the basic concepts are all there - should I spend the time to
finish it? Any major concerns about the design or names?

—
Reply to this email directly or view it on GitHub
https://github.com/plusvic/yara/issues/33#issuecomment-187022419.

[kallanreed]

Few thoughts

• Part of the idea of the section reader was that it would keep the process open between calls (mainly a problem for Windows I suppose). Opening the process for each block would help detect a closed process better than a failed memory read but it would be called a lot (hundreds to thousands of times) per process. I think attaching once per scan is the right approach here.
• I'm currently pre-fetching the VM sections into a linked list. This work could be deferred but it means reparsing the map file multiple times in Linux and I haven't looked closely enough at the BSD code to know what the call pattern would look like. Having the section list makes iteration a lot more straightforward.
• I like the API surface you proposed but I still need to get error codes out if work is deferred. Is result = iterator->next(iterator, &block) reasonable?
• In the fetch_block case, does the block need to be passed in? The iterator will have to know which block its pointing at so the parameter seems redundant.
• I like the signature of fetch_block (returning the pointer) but I'm left with the problem of error codes again. If the signature were int fetch_block(char** data) that would imply that the returned structure be freed by the caller which is not the case in for a linked list. We could simply return null on failure but that hides some potential errors. In the case of the deferred read, there needs to be something that frees the previously allocated block data. Currently blocks are freed by the section reader's read_next_section - this is what keeps memory usage down but it also implies that you cannot hold onto data between calls to next during iteration unless you make a copy.
• If the iteration and fetching are separated, the MEMORY_BLOCK data field will be null in the case of deferred reading, not terrible but maybe warrants a type without the field? No for now.

Given the above, we need the following types

• BLOCK_ITERATOR more or less as you described caveat the error handling
• LIST_ITERATOR_CONTEXT to hold a list head and current pointers
• PROCESS_ITERATOR_CONTEXT to hold the attached process context, a LIST_ITERATOR_CONTEXT of the sections, and the current data buffer.
• The SECTION_READER and MEMORY_SECTION types would go away.

EDIT: I think I have an idea that will work. I'll send out an update soon.

[plusvic]

• Part of the idea of the section reader was that it would keep the
  process open between calls (mainly a problem for Windows I suppose).
  Opening the process for each block would help detect a closed process
  better than a failed memory read but it would be called a lot (hundreds to
  thousands of times) per process. I think attaching once per scan is the
  right approach here.

You don't need to open the process for each block, you open the process
once in yr_rules_scan_proc and store the handle in some struct pointed by
the context pointer un YR_BLOCK_ITERATOR. Each time you call to
iterator->next(iterator) the next function gets the handle from the context
pointer.

• I'm currently pre-fetching the VM sections into a linked list. This
  work could be deferred but it means reparsing the map file multiple times
  in Linux and I haven't looked closely enough at the BSD code to know what
  the call pattern would look like. Having the section list makes iteration a
  lot more straightforward.

You can do the same thing here, you can pre-fetch the list of VM sections
and store it in the context, and store a pointer to the current section
too. Calls to iterator->next(iterator) will just return the current section
and move the current pointer to the next one.

• In the fetch_block case, does the block need to be passed in? The
  iterator will have to know which block its pointing at so the parameter
  seems redundant.

Yes, that's true.

• I like the signature of fetch_block (returning the pointer) but I'm
  left with the problem of error codes again. If the signature were int
  fetch_block(char** data) that would imply that the returned structure be
  freed by the caller which is not the case in for a linked list. We could
  simply return null on failure but that hides some potential errors. In
  the case of the deferred read, there needs to be something that frees the
  previously allocated block data. Currently blocks are freed by the section
  reader's read_next_section - this is what keeps memory usage down but it
  also implies that you cannot hold onto data between calls
  to next during iteration unless you make a copy.

We can use int fetch_block(char** data) this doesn't means that the caller
is responsible for freeing the data, the caller is just providing a place
where the callee is going to store a pointer to the data. The callee can
still be the owner of the data. The previously allocated data can be freed
in the next call to iterator->next(iterator), just like you do now. As you
mention, the data returned by fetch_block is only valid until the next call
to iterator->next(iterator), that's a reasonable behaviour for an iterator,
once you move forward to the next element you don't have access to the
previous one anymore.

• If the iteration and fetching are separated, the MEMORY_BLOCK data
  field will be null in the case of deferred reading, not terrible but maybe
  warrants a type without the field? No for now.

Yes, the idea is removing the "data" field from MEMORY_BLOCK, and accessing
the data by calling fetch_block

PROCESS_ITERATOR_CONTEXT to hold the attached process context, a
LIST_ITERATOR_CONTEXT of the sections, and the current data buffer.

We need a PROCESS_ITERATOR_CONTEXT for iterating over the process sections,
but I don't understand why you need another iterator type for this. Of
course we need another iterator type for scanning files, but those will be
pretty straightforward as they consists of single block, and we don't need
it for scanning processes.

On Mon, Feb 22, 2016 at 4:56 PM, Kyle Reed notifications@github.com wrote:

Few thoughts

• Part of the idea of the section reader was that it would keep the
  process open between calls (mainly a problem for Windows I suppose).
  Opening the process for each block would help detect a closed process
  better than a failed memory read but it would be called a lot (hundreds to
  thousands of times) per process. I think attaching once per scan is the
  right approach here.
• I'm currently pre-fetching the VM sections into a linked list. This
  work could be deferred but it means reparsing the map file multiple times
  in Linux and I haven't looked closely enough at the BSD code to know what
  the call pattern would look like. Having the section list makes iteration a
  lot more straightforward.
• I like the API surface you proposed but I still need to get error
  codes out if work is deferred. Is result = iterator->next(iterator,
  &block) reasonable?
• In the fetch_block case, does the block need to be passed in? The
  iterator will have to know which block its pointing at so the parameter
  seems redundant.
• I like the signature of fetch_block (returning the pointer) but I'm
  left with the problem of error codes again. If the signature were int
  fetch_block(char** data) that would imply that the returned structure
  be freed by the caller which is not the case in for a linked list. We could
  simply return null on failure but that hides some potential errors. In
  the case of the deferred read, there needs to be something that frees the
  previously allocated block data. Currently blocks are freed by the section
  reader's read_next_section - this is what keeps memory usage down but
  it also implies that you cannot hold onto data between calls to next
  during iteration unless you make a copy.
• If the iteration and fetching are separated, the MEMORY_BLOCK data
  field will be null in the case of deferred reading, not terrible but maybe
  warrants a type without the field? No for now.

Given the above, we need the following types

• BLOCK_ITERATOR more or less as you described caveat the error
  handling

• LIST_ITERATOR_CONTEXT to hold a list head and current pointers

  PROCESS_ITERATOR_CONTEXT to hold the attached process context, a

  LIST_ITERATOR_CONTEXT of the sections, and the current data buffer.

  The SECTION_READER and MEMORY_SECTION types would go away.

—
Reply to this email directly or view it on GitHub
https://github.com/plusvic/yara/issues/33#issuecomment-187242350.

[kallanreed]

I started a the impl of the design and ran into some issues. Some of which you addressed above, I added some comments in the commit.

1. re: keeping the process open while iterating - I just wanted to make sure we were on the same page.

2. re: prefetching removes the need for error checking on the block first/next interface because all of the operations that could fail happen when the iterator is opened and when it's closed. Fetch could still fail.

3. I didn't realize you wanted to remove the data member from YR_MEMORY_BLOCK. That type is used everywhere and I think that would be an invasive change. Also, in order for that to work, everywhere we would either need to keep the context in the block as well as the read function or update every place a block is used to take an ITERATOR instead.

I was considering a second type like YR_DEFERRED_BLOCK which is like the normal block without the data field. This way the existing code that expects blocks could be left alone for now.

4. I see what you mean about the LIST_ITERATOR_CONTEXT I didn't notice that the reason I added it at all was to support the thing I'm removing (yr_process_get_memory). I'll still need implementations for first/next/fetch for a single block but the type can go away.

[plusvic]

3. I didn't realize you wanted to remove the data member from
   YR_MEMORY_BLOCK. That type is used everywhere and I think that would be an
   invasive change. Also, in order for that to work, everywhere we would
   either need to keep the context in the block as well as the read function
   or update every place a block is used to take an ITERATOR instead.

Yes, block->data in some modules, and in exec.c, but in all cases can be
easily changed to use the iterator and fetch_block. I prefer keeping
everything coherent and simple even if we have to refactor a few things.

On Mon, Feb 22, 2016 at 8:43 PM, Kyle Reed notifications@github.com wrote:

I started a the impl of the design
kallanreed@4b2a8cb?diff=split
and ran into some issues. Some of which you addressed above, I added some
comments in the commit.

1. re: keeping the process open while iterating - I just wanted to make
   sure we were on the same page.

2. re: prefetching removes the need for error checking on the block
   first/next interface because all of the operations that could fail happen
   when the iterator is opened and when it's closed. Fetch could still fail.

3. I didn't realize you wanted to remove the data member from
   YR_MEMORY_BLOCK. That type is used everywhere and I think that would be
   an invasive change. Also, in order for that to work, everywhere we would
   either need to keep the context in the block as well as the read function
   or update every place a block is used to take an ITERATOR instead.

I was considering a second type like YR_DEFERRED_BLOCK which is like the
normal block without the data field. This way the existing code that
expects blocks could be left alone for now.

4. I see what you mean about the LIST_ITERATOR_CONTEXT I didn't notice
   that the reason I added it at all was to support the thing I'm removing
   (yr_process_get_memory). I'll still need implementations for
   first/next/fetch for a single block but the type can go away.

—
Reply to this email directly or view it on GitHub
https://github.com/plusvic/yara/issues/33#issuecomment-187344694.

[kallanreed]

Sounds good. I'll give that a try.

[kallanreed]

Block iterator everywhere

Here's what the change to add the block iterator everywhere looks like. I tried to minimize the touch, but I had to add null checks after fetch and (hopefully) do the right thing on failure. This does not include the new process reader yet but you know how that's going to look.

My only concern is that before, reading process memory was done once at the expense of memory. Now if there are multiple modules enabled, process memory will be read multiple times - adding to CPU usage. As you mentioned, not all modules actually read all blocks so it may not be that bad.

I'm concerned by the amount of size of this change. How are big changes normally tested?

EDIT:
I haven't dug into how the modules or exec are called but if they reuse the iterator that yr_scan_mem_blocks is using in its while loop from within the loop, the iterator state will be invalid for the top loop. I need to dig in more and figure out if we have to worry about that and if so, we'll need to stick a copy of the iterator on the scan context. We'll just have to be careful not to close the underlying proc handle either with a copy or with the original but before the copy has finished.

[kallanreed]

@plusvic this is working for Windows. I verified that there aren't any cases where the iterator used for a loop is invalidated by a call to a module. Take a look at the diff and let me know what you think. If it looks good I'll finish it for Linux and BSD.

[kallanreed]

@plusvic I submitted PR #418 with this change. Haven't heard anything for a few weeks and wanted to see if there was anything wrong with the change.

[plusvic]

@kallanreed sorry for not answered before, I've been very busy these days. Yes, I've found a problem that we haven't solved yet. The YR_MATCH structure has a field named data which is a pointer to the matching string and it points into a YR_MEMORY_BLOCK. Clients of libyara use the pointer assuming that it's safe to access that memory, but with the current approach that's no true anymore.

We need to solve that issue before merging these changes. I haven't thought about the best solution yet, but if you have any proposal please tell me.

[kallanreed]

So I'm clear, the bug is here in scan_mem_blocks:

  yr_rules_foreach(rules, rule)
  {
    int message;

    if (rule->t_flags[tidx] & RULE_TFLAGS_MATCH &&
        !(rule->ns->t_flags[tidx] & NAMESPACE_TFLAGS_UNSATISFIED_GLOBAL))
    {
      message = CALLBACK_MSG_RULE_MATCHING;
    }
    else
    {
      message = CALLBACK_MSG_RULE_NOT_MATCHING;
    }

    if (!RULE_IS_PRIVATE(rule))
    {
      switch (callback(message, rule, user_data))
      {
        case CALLBACK_ABORT:
          result = ERROR_SUCCESS;
          goto _exit;

        case CALLBACK_ERROR:
          result = ERROR_CALLBACK_ERROR;
          goto _exit;
      }
    }
  }

The problem is that the callback is passed a rule which contains a pointer to the freed block. I don't quite understand how the rule references the match (the arena?) but I think I understand the issue. I can repro with -s.

Are there any other places the callback will be called with match data that I'm missing? I didn't think so after a quick check.

@plusvic Few top of mind thoughts:

1. Move all of the actions to take on a block inside of a single loop. It looks like scan and exec would behave the same way but the callback would be called (rules * block) times. This would probably break assumptions made by code using libyara. For file matching there wouldn't be extra callbacks.
2. Copy matching memory into the YR_MATCH. This would mainly solve the problem but I don't know what "unconfirmed" chain_length implies. The downside is that this could potentially use even more memory and certainly would be worse for the file matching case. Obviously there would be more allocations.
3. Ref count the pointers to the blocks and don't free blocks if they are used in a match. Memory use will be dependent on rule matches. It shouldn't have any impact on libyara users. On the downside, it's would be hand-rolled ref counting.
   I'm assuming there's some reason that C++ isn't used in the code currently, however if there isn't shared_ptr would be helpful instead of hand-rolling ref counting.

[plusvic]

This issue was solved. See #418.