Bitdefender: Remote Stack Buffer Overflow via 7z PPMD

If you read my previous blog post and were bored by it, then this might be for you. With the second post of the series, I am delivering on the promise of discussing a bug that occurs in a more complex setting.

A bug in a software module that extracts a prominent archive format (such as 7z) needs to be treated with great caution. It is often critical not only for the software itself, but also for many different software products that are sharing the same library or are based on the same reference implementation.

So, to address this issue right up front: I believe this bug does not affect Igor Pavlov’s 7z reference implementation¹. However, it would not surprise me if products other than Bitdefender were affected by this.

Introduction

After having found critical bugs in anti-virus products of smaller vendors, I eventually decided to have a look at Bitdefender’s anti-virus product. Therefore, I started fuzzing the engine and after a while I had the first crashes, which involved the 7z file format.

7z is quite complex. The file format itself is non-trivial, and the many compression methods it supports are so, too.

Fortunately, only some parts of the file format and the so-called PPMd codec are relevant to this bug. PPMd is a compression algorithm originally developed by Dmitry Shkarin². It makes use of prediction by partial matching³ and combines it with range encoding⁴.

In essence, prediction by partial matching is the idea of building a model that tries to predict the next symbol given the n previous symbols. The context stores the sequence consisting of the last n symbols, and the constant n is called the order of the model.

I hope that this basic information will suffice to understand what follows. In case you like to read more about PPM, I strongly recommend the paper by Cleary and Witten⁵. Alternatively, Mark Nelson’s blog post⁶ is a great read, too.

Getting Into the Details

Debugging a crash that occurs deep in 7z code of an anti-virus product is a nightmare if you have no symbols.

A possible remedy is to take the reference implementation and try to match the function names. Even though Bitdefender seems to reuse⁷ 7-Zip code, it is not exactly trivial to do this, because the compiler has applied a lot of inlining and even interprocedural optimization.

Having matched the most important 7-Zip functions, we can step through carefully with WinDbg and easily observe that there is an overflow of the stack-allocated ps buffer in the function CreateSuccessors.

In the most recent 7-Zip version, the (first half of the) function looks as follows⁸.

static CTX_PTR CreateSuccessors(CPpmd7 *p, Bool skip) {
  CPpmd_State upState;
  CTX_PTR c = p->MinContext;
  CPpmd_Byte_Ref upBranch = (CPpmd_Byte_Ref)SUCCESSOR(p->FoundState);
  CPpmd_State *ps[PPMD7_MAX_ORDER]; /* PPMD7_MAX_ORDER==64 */
  unsigned numPs = 0;
  
  if (!skip) { ps[numPs++] = p->FoundState; }
  
  while (c->Suffix) {
    CPpmd_Void_Ref successor;
    CPpmd_State *s;
    c = SUFFIX(c); /* SUFFIX(c) == c->Suffix */
    if (c->NumStats != 1) {
      for (s = STATS(c); s->Symbol != p->FoundState->Symbol; s++);
    } else {
      s = ONE_STATE(c);
    }
    successor = SUCCESSOR(s);
    if (successor != upBranch) {
      c = CTX(successor);
      if (numPs == 0) return c;
      break;
    }
    ps[numPs++] = s;
  }
  
  /* ### Rest of function omitted. ### */
}

We see that the current context (a linked list) is traversed, filling the ps buffer.

It is striking that there is no bound check whatsoever. So, if this is the code from the original 7-Zip implementation, can this be correct?

Recall that the order of the model is the number of symbols that can be stored in the context. If the context is always updated correctly, it should never contain more elements than the order of the model.

So how is a correct update ensured? No matter what the actual mechanism is, it will definitely need to know the order of the model. The name PPMD7_MAX_ORDER is already hinting at the fact that 64 is the maximum order. The actual order, however, may be different. The 7-Zip source code reveals what we are looking for⁹.

STDMETHODIMP CDecoder::SetDecoderProperties2(const Byte *props, UInt32 size) {
  if (size < 5) { return E_INVALIDARG; }
  _order = props[0]; // <---------------------------------
  UInt32 memSize = GetUi32(props + 1);
  if (_order < PPMD7_MIN_ORDER ||
      _order > PPMD7_MAX_ORDER ||
      memSize < PPMD7_MIN_MEM_SIZE ||
      memSize > PPMD7_MAX_MEM_SIZE)
    return E_NOTIMPL;
  if (!_inStream.Alloc(1 << 20)) { return E_OUTOFMEMORY; }
  if (!Ppmd7_Alloc(&_ppmd, memSize, &g_BigAlloc)) { return E_OUTOFMEMORY };
  return S_OK;
}

(Note that this is not the code running in Bitdefender’s engine)

We see that the order is read from the props array. As it turns out, props is read directly from the input file. More specifically, this is the Properties array contained in the Folder structure of 7z’s file format¹⁰.

Moreover, we see that the reference implementation makes sure that the order is not greater than PPMD7_MAX_ORDER.

The order byte of my crashing input is 0x5D, and Bitdefender’s 7z module extracts it anyway. Hence, they omitted this check. This results in a stack buffer overflow.

On Attacker Control

The attacker can fully control the order byte, the maximum order being 255. This allows her to insert up to 255 pointers into the buffer, 191 of which are out of bound. Those pointers point to CPpmd_State structs of the following type (defined in Ppmd.h).

typedef struct {
  Byte Symbol;
  Byte Freq;
  UInt16 SuccessorLow;
  UInt16 SuccessorHigh;
} CPpmd_State;

Note that all struct members are attacker controlled.

Exploitation and Impact

Bitdefender uses a stack canary, as well as ASLR and DEP.

Interestingly, they do not seem to use SafeSEH for a large part of the system. The reason for this is that Bitdefender’s core dynamically loads most of its modules (such as the 7z module) from binary plug-in files which are in a proprietary binary format (i.e., they are not Windows DLLs). More specifically, the engine contains a loader that allocates memory, reads the plug-in files from the file system, decrypts and decompresses them, and then finally relocates the code. Hence, they do not use the Windows PE image loader for a large fraction of the executed code, making it very difficult (if not impossible) to use the full SafeSEH protection mechanism. It seems that they work around this restriction by avoiding the use of exceptions within code of their plug-ins.¹¹

The engine runs unsandboxed and as NT Authority\SYSTEM. Moreover, since the software uses a file system minifilter, this vulnerability can be easily exploited remotely, for example by sending an e-mail with a crafted file as attachment to the victim.

Note also that Bitdefender’s engine is licensed to many different anti-virus vendors such as F-Secure or G Data, all of which could be affected by this bug.¹²

The Fix

Bitdefender decided to fix the bug by ensuring that the function CreateSuccessors throws an error as soon as the variable numPs (index into the ps buffer) reaches the value PPMD7_MAX_ORDER. They still accept an order greater than PPMD7_MAX_ORDER, but the extraction process aborts at the point just when numPs==PPMD7_MAX_ORDER.

This kind of design choice is common practice in the anti-virus industry. They all like to parse and process files in a relaxed fashion. In particular, they are inclined to accept various kinds of (partially) invalid files.

The reason for this is essentially that there exist many different variants of consumer software processing popular file formats (such as rar, zip or 7z). The aim of relaxed file parsing and processing is to cover as many implementations as possible, and to avoid the scenario in which the anti-virus product is dismissing a file as invalid that then is successfully processed by some consumer software.

Considering this mindset when it comes to invalid files, it may very well be that the check of the PPMd order has been omitted deliberately in the first place.

Conclusion

We have seen that it can be challenging to incorporate external code into your software without introducing critical bugs.

When you cannot avoid using external C/C++ code, you should review it with utmost diligence. This bug, for example, could have been caught quite easily by a thorough review.

Note also that it requires a rather involved argument to explain why the buffer in CreateSuccessors cannot overflow, given that the order is not greater than PPMD7_MAX_ORDER. I do not even try to make such an argument, because I believe it should not be required. If the function being free from buffer overflows strongly depends on several other functions and how they update the state, are we not doing something terribly wrong?

Do you have any comments, feedback, doubts, or complaints? I would love to hear them. You can find my e-mail address on the about page.

Timeline of Disclosure

• 2017-02-11 - Discovery
• 2017-02-13 - “Thank you for your report, we will investigate and come back with an answer.”
• 2017-02-21 - Confirmed and patch rolled out
• 2017-02-28 - Bug bounty paid

Thanks & Acknowledgements

I want to thank Bitdefender and especially Marius for their fast response as well as their quick patch. In today’s anti-virus industry, this is (unfortunately) not something that can be taken for granted.

Test File

If you would like to test quickly whether a 7z implementation might be vulnerable, you can try to let it extract this test archive. It is a 7z archive, containing a file foo.txt which itself contains the ASCII string bar. foo.txt is compressed using PPMd with order 65 (recall that PPMD7_MAX_ORDER==64 in the reference implementation).

Note that this file will not cause a stack buffer overflow with the reference implementation even if the order is not checked properly. However, in case a system extracts the file foo.txt successfully (recovering the string bar), this is a strong indication that the order is not checked properly and you should investigate further whether it is vulnerable to the stack buffer overflow or not.