Crash during liveness analysis

[ea]

Hi

I just updated to the latest release and spoted a crashing bug with a certain binary.
The crash happens on : https://github.com/dyninst/dyninst/blob/master/dataflowAPI/src/liveness.C#L473

and again on https://github.com/dyninst/dyninst/blob/master/dataflowAPI/src/liveness.C#L510

Both times the similar code

    else{
      base = changeIfMMX(base);
      ret.read[getIndex(base)] = true;
    }

For some cases , getIndex(base) will return -1 , which will cause an out of bounds access leading to segfault.
This is the crash i get:

Program received signal SIGSEGV, Segmentation fault.
LivenessAnalyzer::calcRWSets (this=0xb7fbf040 <instPoint::liveRegisters()::live1>, curInsn=..., blk=0xc7e35d4, a=158710)
   at dyninst/dyninst-9.2.0/dataflowAPI/src/liveness.C:473
473           ret.read[getIndex(base)] = true;
(gdb) x/i $pc
=> 0xb744d95c <LivenessAnalyzer::calcRWSets(boost::shared_ptr<Dyninst::InstructionAPI::Instruction>, Dyninst::ParseAPI::Block*, unsigned long)+1308>:   or     %edx,(%eax,%edi,4)
(gdb) i r eax edi
eax            0x162ccc50       372034640
edi            0x7ffffff        134217727
(gdb)

I tried to enable liveness debug output, but the offending binary is big and the liveness debug log is getting huge. I'll update the issue once I isolate the problematic instruction/code.

Cheers

[ea]

Here's a sample liveness debug log:

---------------------
        summarize block info at block 8089b2d
liveness.C[145] After instruction vmovdqa <INVALID_REG>, <INVALID_REG>, <INVALID_REG> at address 0x8089b2d:
calcRWSets for vmovdqa <INVALID_REG>, <INVALID_REG>, <INVALID_REG> @ 8089b2d
Read registers:
        <INVALID_REG>
        <INVALID_REG>
Write Registers:
        <INVALID_REG>
liveness.C[157] After instruction at address 0x8089b2d:
-----------------------

So this all seems to be related t o AVX instructions...
These aren't supported? Can they be handled gracefully ?

[jdetter]

Could I have access to the binary you're getting this crash on?

[jdetter]

Also if you could provide me with your os and library versions, that would be helpful,

• Linux version + distribution version
• Boost version
• libdwarf version

Update: Also what GCC are you building with?

[wrwilliams]

@jdetter I would bet that this is reproducible with parseThat -i3 on any of our VEX test binaries.

[jdetter]

@wrwilliams yup I was able to get it to seg fault.

[jdetter]

Somehow I am getting a different error than @ea is reporting. When I run parseThat without gdb it crashes with an assert but when I run it with gdb it finishes without an issue. @wrwilliams any idea why that would be?

[wrwilliams]

That smells like uninitialized memory to me. valgrind have anything useful to say for itself here?

[jdetter]

Looks like there aren't any memory errors, but that at least got me a stacktrace:

[detter@localhost tmp]$ valgrind parseThat -S -i 3 --binary-edit=./ssh /usr/bin/ssh > /dev/null
==24635== Memcheck, a memory error detector
==24635== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==24635== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==24635== Command: parseThat -S -i 3 --binary-edit=./ssh /usr/bin/ssh
==24635==
parseThat: /home/detter/Workspace/dyninst/dataflowAPI/src/liveness.C:67: const bitArray& LivenessAnalyzer::getLivenessIn(Dyninst::ParseAPI::Block*): Assertion `blockLiveInfo.find(block) != blockLiveInfo.end()' failed.
==24635==
==24635== Process terminating with default action of signal 6 (SIGABRT)
==24635==    at 0x5F86A28: raise (in /usr/lib64/libc-2.22.so)
==24635==    by 0x5F88629: abort (in /usr/lib64/libc-2.22.so)
==24635==    by 0x5F7F226: __assert_fail_base (in /usr/lib64/libc-2.22.so)
==24635==    by 0x5F7F2D1: __assert_fail (in /usr/lib64/libc-2.22.so)
==24635==    by 0x7079D69: LivenessAnalyzer::getLivenessIn(Dyninst::ParseAPI::Block*) (liveness.C:67)
==24635==    by 0x7079EB0: LivenessAnalyzer::processEdgeLiveness(Dyninst::ParseAPI::Edge*, livenessData&, Dyninst::ParseAPI::Block*, boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > const&) (liveness.C:87)
==24635==    by 0x7084472: boost::_mfi::mf4<void, LivenessAnalyzer, Dyninst::ParseAPI::Edge*, livenessData&, Dyninst::ParseAPI::Block*, boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > const&>::operator()(LivenessAnalyzer*, Dyninst::ParseAPI::Edge*, livenessData&, Dyninst::ParseAPI::Block*, boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > const&) const (mem_fn_template.hpp:506)
==24635==    by 0x70824ED: void boost::_bi::list5<boost::_bi::value<LivenessAnalyzer*>, boost::arg<1>, boost::reference_wrapper<livenessData>, boost::_bi::value<Dyninst::ParseAPI::Block*>, boost::reference_wrapper<boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > > >::operator()<boost::_mfi::mf4<void, LivenessAnalyzer, Dyninst::ParseAPI::Edge*, livenessData&, Dyninst::ParseAPI::Block*, boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > const&>, boost::_bi::list1<Dyninst::ParseAPI::Edge* const&> >(boost::_bi::type<void>, boost::_mfi::mf4<void, LivenessAnalyzer, Dyninst::ParseAPI::Edge*, livenessData&, Dyninst::ParseAPI::Block*, boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > const&>&, boost::_bi::list1<Dyninst::ParseAPI::Edge* const&>&, int) (bind.hpp:525)
==24635==    by 0x7080A4F: void boost::_bi::bind_t<void, boost::_mfi::mf4<void, LivenessAnalyzer, Dyninst::ParseAPI::Edge*, livenessData&, Dyninst::ParseAPI::Block*, boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > const&>, boost::_bi::list5<boost::_bi::value<LivenessAnalyzer*>, boost::arg<1>, boost::reference_wrapper<livenessData>, boost::_bi::value<Dyninst::ParseAPI::Block*>, boost::reference_wrapper<boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > > > >::operator()<Dyninst::ParseAPI::Edge* const&>(Dyninst::ParseAPI::Edge* const&) (bind.hpp:905)
==24635==    by 0x707F913: boost::_bi::bind_t<void, boost::_mfi::mf4<void, LivenessAnalyzer, Dyninst::ParseAPI::Edge*, livenessData&, Dyninst::ParseAPI::Block*, boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > const&>, boost::_bi::list5<boost::_bi::value<LivenessAnalyzer*>, boost::arg<1>, boost::reference_wrapper<livenessData>, boost::_bi::value<Dyninst::ParseAPI::Block*>, boost::reference_wrapper<boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > > > > std::for_each<boost::iterators::filter_iterator<Dyninst::ParseAPI::Intraproc, __gnu_cxx::__normal_iterator<Dyninst::ParseAPI::Edge* const*, std::vector<Dyninst::ParseAPI::Edge*, std::allocator<Dyninst::ParseAPI::Edge*> > > >, boost::_bi::bind_t<void, boost::_mfi::mf4<void, LivenessAnalyzer, Dyninst::ParseAPI::Edge*, livenessData&, Dyninst::ParseAPI::Block*, boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > const&>, boost::_bi::list5<boost::_bi::value<LivenessAnalyzer*>, boost::arg<1>, boost::reference_wrapper<livenessData>, boost::_bi::value<Dyninst::ParseAPI::Block*>, boost::reference_wrapper<boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > > > > >(boost::iterators::filter_iterator<Dyninst::ParseAPI::Intraproc, __gnu_cxx::__normal_iterator<Dyninst::ParseAPI::Edge* const*, std::vector<Dyninst::ParseAPI::Edge*, std::allocator<Dyninst::ParseAPI::Edge*> > > >, boost::iterators::filter_iterator<Dyninst::ParseAPI::Intraproc, __gnu_cxx::__normal_iterator<Dyninst::ParseAPI::Edge* const*, std::vector<Dyninst::ParseAPI::Edge*, std::allocator<Dyninst::ParseAPI::Edge*> > > >, boost::_bi::bind_t<void, boost::_mfi::mf4<void, LivenessAnalyzer, Dyninst::ParseAPI::Edge*, livenessData&, Dyninst::ParseAPI::Block*, boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > const&>, boost::_bi::list5<boost::_bi::value<LivenessAnalyzer*>, boost::arg<1>, boost::reference_wrapper<livenessData>, boost::_bi::value<Dyninst::ParseAPI::Block*>, boost::reference_wrapper<boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> > > > >) (stl_algo.h:3767)
==24635==    by 0x707A3B1: LivenessAnalyzer::getLivenessOut(Dyninst::ParseAPI::Block*, boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> >&) (liveness.C:116)
==24635==    by 0x707B065: LivenessAnalyzer::updateBlockLivenessInfo(Dyninst::ParseAPI::Block*, boost::dynamic_bitset<unsigned long, std::allocator<unsigned long> >&) (liveness.C:195)
==24635==
==24635== HEAP SUMMARY:
==24635==     in use at exit: 230,623,046 bytes in 3,186,871 blocks
==24635==   total heap usage: 10,144,481 allocs, 6,957,610 frees, 517,179,621 bytes allocated
==24635==
==24635== LEAK SUMMARY:
==24635==    definitely lost: 295,728 bytes in 2,624 blocks
==24635==    indirectly lost: 1,398,586 bytes in 27,816 blocks
==24635==      possibly lost: 1,268,337 bytes in 26,896 blocks
==24635==    still reachable: 227,587,691 bytes in 3,129,534 blocks
==24635==                       of which reachable via heuristic:
==24635==                         newarray           : 528 bytes in 1 blocks
==24635==                         multipleinheritance: 5,422,304 bytes in 23,372 blocks
==24635==         suppressed: 72,704 bytes in 1 blocks
==24635== Rerun with --leak-check=full to see details of leaked memory
==24635==
==24635== For counts of detected and suppressed errors, rerun with: -v
==24635== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

[jdetter]

This is the code block causing the issue for me. The first assert fails.

const bitArray& LivenessAnalyzer::getLivenessIn(Block *block) {
    // Calculate if it hasn't been done already
    liveness_cerr << "Getting liveness for block " << hex << block->start() << dec << endl;
    assert(blockLiveInfo.find(block) != blockLiveInfo.end());
    livenessData& data = blockLiveInfo[block];
    assert(data.in.size());
    return data.in;
}

[wrwilliams]

...comment does not match code. @mxz297, you know off the top of your head what's up here?

[jdetter]

I added some more asserts in the liveness analysis that probably should have been there (checks to make sure array indexes are greater than 0). This should at least cause asserts instead of silent failures and buffer overreads. I think I need more environment and binary information from @ea to reproduce his specific issue.

[jdetter]

This issue has been frustratingly difficult to debug, primarily because the bug doesn't appear every run and it never appears when ran through gdb (at least for me). I talked with Xiaozhu and he said he would be able to look at this sometime this week.

[ea]

Did you get my offlist email ?

[jdetter]

@ea unfortunately I did not, did you send it to jdetter@wisc.edu?

[ea]

forwarded, please check spam :)

[mxz297]

What @jdetter has seen is mainly caused by an issue of inconsistent CFG labeling.

Basically, we somehow did not finalize a function after parsing it. So, the function had an incomplete basic block list. In liveness analysis, we first calculated block summaries based on this incomplete block list. Then when we were performing the fix point analysis, we visited a block that was truly in this function, but was not included in the basic block list.

However, in the end, I think the issue reported by @ea is different issue from this inconsistent CFG issue. I will first fix the inconsistent CFG issue first and then see what we have.

[mxz297]

Now I believe I have fixed the inconsistent CFG issue. But I cannot reproduce the issue reported by @ea on any VEX binaries (running parseThat -i3 on xhpl or hpgmg-fv seems to be fine). @jdetter Do you have the exact binary and could you send it to me if you have?

[mxz297]

I am now able to reproduce the exact crash. I will get to you @ea when I have a better idea of what's the problem.

[mxz297]

@jdetter The issue is that we do not represent ymm registers for 32-bit binaries. The offending instruction is

8089b2d: c5 fd 6f ca vmovdqa %ymm2,%ymm1

In common/h/dyn_regs.h and dataflowAPI/src/RegisterMap.C, we have code for representing ymm registers for 64-bit binaries, but we do not have any code for representing ymm registers for 32-bit binaries.

[jdetter]

I'm rebuilding/rerunning in a 32 bit environment to make sure the patch works, but so far it looks like I have it fixed.

[ea]

Rebuilding too and will try against my target binary ASAP and report back. Thanks!

[jdetter]

@ea the patch is available on branch release9.2/fixes/liveness-patch but should make it into release9.2_patches soon.

[jdetter]

This is now available on v9.2_patches. Will be eventually merged over to master.

[jdetter]

The fix for this issue must be moved into v9.3.0 because of ABI issues, checks will be added to assert when we hit this bug in the next minor release v9.2.1.