Cryptopp: Calling multiple ZlibDecompressor in parallel causes adler32 checksum failure

[rocksonhead]

msvc 15, 17 and gcc 5.4 64bit compilers
crypto versions 5.6.5 and 6.1
built via cmake on gcc 5.6.5
and vs projects on 5.6.5 and 6.1 - though changing runtime library to /MD
Please see attached project for example code to induce failure on windows.

The failure may not occur on the first run, but running the application several times an exception is thrown in the decompression "Adler32 check error"

The example code uses openmp to parallelize, however it can also be replicated using tbb

test.zip

[rocksonhead]

The failure seems to be occurring somewhere around the HuffmanDecoder::Decode
This function is returning 0 lengths.
The message is not printed when performing 1 decompression or in debug mode.

inline unsigned int HuffmanDecoder::Decode(code_t code, /* out */ value_t &value) const
{
    CRYPTOPP_ASSERT(m_codeToValue.size() > 0);
    LookupEntry &entry = m_cache[code & m_cacheMask];
    code_t normalizedCode = 0;

    if (entry.type != 1)
    {
        normalizedCode = BitReverse(code);
    }

    if (entry.type == 0)
    {
        FillCacheEntry(entry, normalizedCode);
    }

    if (entry.type == 1)
    {
        value = entry.value;
        if (entry.len == 0)
            std::cout << "\nDecode failed" << std::flush;
        return entry.len;
    }
    else
    {
        const CodeInfo &codeInfo = (entry.type == 2)
            ? entry.begin[(normalizedCode << m_cacheBits) >> (MAX_CODE_BITS - (entry.len - m_cacheBits))]
            : *(std::upper_bound(entry.begin, entry.end, normalizedCode, CodeLessThan())-1);
        value = codeInfo.value;
        return codeInfo.len;
    }
}

[noloader]

Thanks @rocksonhead.

I took a quick look at your test case and nothing jumped out at me. I hope to take a deeper look later this week.

One thing worth mentioning is, all Crypto++ classes are intended to be thread safe at the object level. Generally speaking, that means there is no shared state among objects. If multiple threads share the same object then the caller is responsible for locking.

Looking at your sample code it looks like each thread gets its own compressor and decompressor so thread safety should be an emergent property, without the need for extra goodness like locks.

I've seen some initialization races on occasion. Usually the race was in the encoders and decoders because they built their encoding and decoding tables on the fly and shared the table among instances. I don't believe the compressors and decompressors share state, but I have not looked closely.

[rocksonhead]

Appreciate it!
Will continue to try and diagnose whats happening in the meantime.
Kind regards

[rocksonhead]

It might be associated with the struct LookupEntry. So far I cannot replicate the problem with an extra param in the struct...

struct LookupEntry
{
    unsigned int type;
    unsigned int hits = 0;
    union
    {
        value_t value;
        const CodeInfo *begin;
    };
    union
    {
        unsigned int len;
        const CodeInfo *end;
    };
};

[noloader]

@rocksonhead,

Be careful of the union. Accessing the inactive member is undefined behavior in C++ (though it is fine in C). Also see Accessing inactive union member and undefined behavior?

I wonder if you are seeing the effects of a wild read or write. Does Valgrind report anything suspicious?

[rocksonhead]

Scratch my comment about the struct - further testing still produces the error :( However the occurence is much reduced.
I cannot get my test application to fail on my windows ubuntu subsystem.

[rocksonhead]

Came at it with a fresh mind this morning and re-read the code.
My current hypothesis is that a race condition is occurring.....

The Inflators - in this case - are using Singleton HuffmanDecoders

const HuffmanDecoder& Inflator::GetLiteralDecoder() const
{
    return m_blockType == 1 ? Singleton<HuffmanDecoder, NewFixedLiteralDecoder>().Ref() : m_dynamicLiteralDecoder;
}

This results in multiple threads accessing the same HuffmanDecoder::Decode simultaneously.
This becomes a problem then both threads are trying to decode the same code.
A reference to the cache entry is retrieved and then filled.

Thread 1 may execute the following

if (entry.type == 0)
   FillCacheEntry(entry, normalizedCode);

upto the point

normalizedCode &= m_normalizedCacheMask;
const CodeInfo &codeInfo = *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode, CodeLessThan())-1);
if (codeInfo.len <= m_cacheBits)
{
    entry.type = 1;

Thread 2, on the same entry then validates:

if (entry.type == 1)
{
    value = entry.value;
    return entry.len;
}

As thread 1 has set the entry type, but not the len, thread 2 evaluates the entry type, and returns an unset entry.len.

I am attempting to validate this by adding an atomic_flag to the LookupEntry struct, to ensure that only 1 thread can update a single cache entry at a time....

[noloader]

Thanks @rocksonhead.

const HuffmanDecoder& Inflator::GetLiteralDecoder() const {
    return m_blockType == 1 ? Singleton<HuffmanDecoder, NewFixedLiteralDecoder>().Ref() : m_dynamicLiteralDecoder;
}

Oh yeah, that could do it.

An example of a similar problem and fix is at Intialization of base64 and other decoders are not threadsafe. If possible, we need to statically allocate the FixedLiteralDecoder. It makes for a bigger executable, but it does not suffer the races.

Good job on tracking it down.

[rocksonhead]

My test using atomic_flag does prove it is possible for this race condition to occur.

I am not conversant in the data created by zlib so I cannot propose a solution that I could be confident as correct, so was wondering if I could get feedback on whether the below would work as a stopgap until a full fix was proposed?

const HuffmanDecoder& Inflator::GetLiteralDecoder() const
{
    if (m_blockType == 1)
    {
        if (m_literalDecoder.get() == NULLPTR)
            m_literalDecoder.reset(NewFixedLiteralDecoder()());
        return *m_literalDecoder;
    }
    else
    {
        return m_dynamicDistanceDecoder;
    }
}

const HuffmanDecoder& Inflator::GetDistanceDecoder() const
{
    if (m_blockType == 1)
    {
        if (m_distanceDecoder.get() == NULLPTR)
            m_distanceDecoder.reset(NewFixedDistanceDecoder()());
        return *m_distanceDecoder;
    }
    else
    {
        return m_dynamicDistanceDecoder;
    }
}

[noloader]

Thanks again @rocksonhead.

I remember reading a comment about these classes when Wei implemented them. Wei said something about a bug when using the reference implementation so he re-wrote it in C++. I find both the reference implementation and the existing code to be hairy and I try to avoid both.

My gut feeling is, there are several problems. First, I think all initialization should occur in HuffmanDecoder::Initialize. It should not defer until HuffmanDecoder::Decode. But I also understand a dynamic code needs to be built on the fly.

Second, I think we might need to stop building the static codes at runtime. That strategy has gotten us in trouble in the past.

Third, if we look at Inflator:

class Inflator
{
    ...
    HuffmanDecoder m_dynamicLiteralDecoder, m_dynamicDistanceDecoder;
};

The Inflator class violates the thread safety we promise by using the Singleton to share data between instances. I think the fix is to re-write these two methods:

const HuffmanDecoder& Inflator::GetLiteralDecoder() const
{
    return m_blockType == 1 ? Singleton<HuffmanDecoder, NewFixedLiteralDecoder>().Ref() : m_dynamicLiteralDecoder;
}

const HuffmanDecoder& Inflator::GetDistanceDecoder() const
{
    return m_blockType == 1 ? Singleton<HuffmanDecoder, NewFixedDistanceDecoder>().Ref() : m_dynamicDistanceDecoder;
}

I'm going to need more time to study this more. Also, let's ping @denisbider, @mouse07410 and @MarcelRaad. They are also maintainers, and they jump in for the non-trivial stuff.

For the long term fix I think we are going to have to do away with the Singleton altogether. We will have to bite the bullet and build FixedLiteralDecoder per-instance when its needed. That should avoid penalizing dynamic codes and maintain the thread safety guarantees.

[denisbider]

Aw, yikes. This looks pretty bad.

After looking at this for perhaps 30 minutes, I see two issues, one in Singleton and one in Inflator / HuffmanDecoder.

The Singleton issue is that the legacy implementation of Singleton::Ref in misc.h - the version that's not C++11 - appears to have a race condition. If I'm seeing it right, this can allow the singleton to be initialized multiple times by separate threads. All but one of the created objects will have their pointers lost and will never be destroyed. But worse, the thread that created each object will return the object it created. Therefore, Singleton::Ref is not guaranteed to return the same object consistently. In a race condition on first access, different threads can get different objects, but only one is the "true" singleton that won the race. This can lead to inconsistency in application state if threads rely on all getting the same object.

This issue can be relatively straightforwardly fixed. The Singleton initialization logic is broken, but it's just a matter of replacing it with more robust logic (that does not have to be any less efficient).

The Inflator / HuffmanDecoder issue though... Oh my. So the situation we have here is that when Inflator::m_blockType equals 1 - a situation controlled by a potential attacker - multiple threads will call Decode on the same HuffmanDecoder instance previously initialized via Singleton::Ref. (Or sometimes perhaps different instances, due to the previous bug in Singleton::Ref, hehe.)

The issue here is that the literal HuffmanDecoder objects are not immutable, and their initialization doesn't fully happen in NewFixedLiteralDecoder or NewFixedDistanceDecoder. The m_cache is not initialized, and its initialization is deferred until some call to Decode occurs that needs a particular m_cache entry.

@noloader, this means your above workaround won't work. If I'm seeing this correctly, it may be that the only safe way that currently exists for a multithreaded application to use Inflator is if the main thread creates an Inflator instance and feeds to it contrived data that will initialize all m_cache entries in both the fixed literal encoder, and the fixed distance encoder, before any other threads are created.

I see the following ways to fix this in zinflate.cpp:

1. High-maintenance, high-risk, but efficient solution. In NewFixedLiteralDecoder and NewFixedDistanceDecoder, after the call to pDecoder->Initialize, insert a bunch of code that can directly invoke this function:

   inline unsigned int HuffmanDecoder::Decode(code_t code, /* out */ value_t &value) const

   ... with parameters crafted to initialize all m_cache entries. This is high-maintenance because if there's any change to HuffmanDecoder internal state, this initialization code needs to be updated as well, and there will be no obvious indication that it needs to be updated. It is high-risk because there may be other delayed initialization that can happen besides m_cache, and there may be a bug in the initialization code that fails to properly initialize all of m_cache.

   However, it is efficient because multiple threads will continue to share the same fixed literal decoder and distance decoder instances.

2. The low-maintenance, low-risk, less efficient, easy to implement solution: Simply make every instance of Inflator use its own fixed literal decoder and fixed distance decoder. That is, create new members m_fixedLiteralDecoder and m_fixedDistanceEncoder, and just use those. Fixed!

3. The low-maintenance, low-risk, medium efficient, harder to implement solution: A variant on 2, but instead of using separate fixed decoders for each Inflator instance, use thread local storage to have separate fixed decoder instances for each thread. Problematic because there are constraints on the availability of thread local storage.

I would go with option 2 to fix Inflator - optimize safety and ease of maintenance at the expense of efficiency. I would also fix the legacy version of Singleton::Ref.

[denisbider]

@rocksonhead: Yes, I think the solution you described in this comment is equivalent to my suggestion 2 in my previous comment, and may perhaps be the most sensible way to fix this in the library, as well.

[denisbider]

@noloader, @rocksonhead:

After studying this a bit more, I am wondering if it's perhaps premature to assume that Wei did not intend HuffmanDecoder to be thread-safe. Given that m_cache is declared mutable:

mutable std::vector<LookupEntry, AllocatorWithCleanup<LookupEntry> > m_cache;

... it seems clear the author intended this to be a special variable which const member methods could safely modify. This is consistent with that Singleton::Ref returns a const reference.

In this light, perhaps all that is wrong is that FillCacheEntry does not actually initialize m_cache safely. My understanding is that the function is already idempotent. So perhaps all that's needed is to make it like this:

void HuffmanDecoder::FillCacheEntry(LookupEntry &entry, code_t normalizedCode) const
{
    normalizedCode &= m_normalizedCacheMask;
    const CodeInfo &codeInfo = *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode, CodeLessThan())-1);
    if (codeInfo.len <= m_cacheBits)
    {
        entry.value = codeInfo.value;
        entry.len = codeInfo.len;
        MEMORY_BARRIER();
        entry.type = 1;
    }
    else
    {
        entry.begin = &codeInfo;
        const CodeInfo *last = & *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode + ~m_normalizedCacheMask, CodeLessThan())-1);
        if (codeInfo.len == last->len)
        {
            entry.len = codeInfo.len;
            MEMORY_BARRIER();
            entry.type = 2;
        }
        else
        {
            entry.end = last+1;
            MEMORY_BARRIER();
            entry.type = 3;
        }
    }
}

That being said, though - I'm not sure whether this means that HuffmanDecoder::Decode would need a MEMORY_BARRIER() after it reads entry.type and before it reads entry.value and entry.len. And if Decode needs a memory barrier, I don't know how much less efficient Decode would become.

If Decode needs a memory barrier, and this would make it less efficient, then that probably defeats the purpose of using the singletons to begin with.

[denisbider]

OK, I have educated myself on MEMORY_BARRIER(). The way this is defined in misc.h, it's a compiler-only memory barrier. It emits no instructions, it just prevents compiler reordering of loads and stores.

I believe this means MEMORY_BARRIER() is close to zero-cost, apart from any avoided optimizations. However, it may not have effect on non-x86/64 platforms, e.g. on ARM, which do not provide the same assurances as x86/64 with regard to the order of memory access.

[rocksonhead]

I have updated the FillCacheEntry to use the MEMORY_BARRIER() and over several thousand iterations of my test case have yet to hit the race.
I'll add the code to our system and run our unit tests.....

[noloader]

@rocksonhead, @denisbider,

I got a better look at @rocksonhead fix in comment 372715474. The formatting made a world of difference (my ISP seems to be caching some sites, so I don't get to see the updates even after refreshing the page). So it looks like we all came to the same conclusion (give or take).

@denisbider, are you OK with @rocksonhead proposed solution? Or do we want to get rid of the Singletons?

If so, @rocksonhead, can you make the PR? You worked hard for it. I think you deserve it.

[rocksonhead]

One last question ;)

Are the function declarations in zinflate.h still required?

static const HuffmanDecoder *FixedLiteralDecoder();
static const HuffmanDecoder *FixedDistanceDecoder();

VS tells me that there is no function body associated with them... and I can not find them either!

[noloader]

@rocksonhead,

The change in comment 372715474 tested good on x86_64, Aarch64 and PPC64-be. However cryptest.sh only tests configurations (and not multiple threads).

I'm OK with a PR if @denisbider is OK with it.

@denisbider - Should NewFixedLiteralDecoder and NewFixedDistanceDecoder be made freestanding functions to avoid this? Something looks odd about it.

m_literalDecoder.reset(NewFixedLiteralDecoder()());

[rocksonhead]

@noloader
Something along the lines ....

```const HuffmanDecoder& Inflator::GetLiteralDecoder() const
{
if (m_blockType == 1)
{
if (m_fixedLiteralDecoder.get() == NULLPTR)
CreateFixedLiteralDecoder();
return *m_fixedLiteralDecoder;
}
else
{
return m_dynamicLiteralDecoder;
}
}

The other thought is that as m_dynamicLiteralDecoder is a member variable - do the same for m_fixedLiteralDecoder. The question is then when to do the once only population, if you are worried about memory overhead of carrying an always initialized instance.

```const HuffmanDecoder& Inflator::GetLiteralDecoder() const
{
    if (m_blockType == 1)
    {
        if ( fixedLiteralDecoder not initialized )
            intialize();
        return m_fixedLiteralDecoder;
    }
    else
    {
        return m_dynamicLiteralDecoder;
    }
}

or

const HuffmanDecoder& Inflator::GetLiteralDecoder() const { return (m_blockType == 1) ? m_fixedLiteralDecoder : m_dynamicLiteralDecoder; }

[denisbider]

@noloader: I resolved this in our copy of Crypto++ (which is used on x86/x64 architectures only) by reordering memory writes in FillCacheEntry and adding compiler memory barriers in FillCacheEntry and Decode. There was no measurable impact on performance.

[noloader]

Cleared at Commit b0f717059556.