search

Quuxplusone / LLVMBugzillaTest

0 stars 0 forks source link

Fuzz llvm-as #24638

Open Quuxplusone opened 9 years ago

Quuxplusone commented 9 years ago
Bugzilla Link PR24639
Status CONFIRMED
Importance P normal
Reported by Karl Schimpf (kschimpf@google.com)
Reported on 2015-08-31 12:23:16 -0700
Last modified on 2015-10-01 16:08:24 -0700
Version trunk
Hardware PC Linux
CC kcc@google.com, krasin@google.com, llvm-bugs@lists.llvm.org, llvm-bugzilla@jfbastien.com
Fixed by commit(s)
Attachments repros.txt (5658 bytes, text/plain)
llvm-as-parasitic-coverage-repro.patch (1817 bytes, text/plain)
Blocks
Blocked by PR24644, PR24657, PR24661, PR24640, PR24645, PR24646, PR24656, PR24662
See also
Quuxplusone commented 9 years ago

This bug is to track bugs found when fuzzing llvm-as. Dependent bugs are bugs found by afl-fuzz, or a lib/Fuzzer version of llvm-as.

Quuxplusone commented 9 years ago

Committed lib/Fuzzer version of llvm-as (i.e. llvm-as-fuzzer). Revision: http://reviews.llvm.org/rL246458

Quuxplusone commented 9 years ago 
The bot (http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fuzzer)
is running llvm-as-fuzzer with -only_ascci=1 and the default max_len (=64).
It uses the build with assertions.

Currently, it fails instantly due to bug 24640

The corpus for the bot is https://github.com/kcc/fuzzing-with-
sanitizers/tree/master/llvm/llvm-as/C1
which was generated by the fuzzer from scratch, with no seed corpus.

Later on we may want to extend the corpus with more valid inputs
and increase the max_len.
Quuxplusone commented 9 years ago 
I've extended the corpus by adding all .ll files from the llmv test suite
and stripping ;.*
It instantly increased the coverage by 2x, still growing

Hitting several asserts so far, e.g.

lib/IR/Globals.cpp:209: void
llvm::GlobalVariable::setInitializer(llvm::Constant *): Assertion `InitVal-
>getType() == getType()->getElementType() && "Initializer type must match
GlobalVariable type"' failed.

llvm/include/llvm/Support/Casting.h:237: typename cast_retty<X, Y *>::ret_type
llvm::cast(Y *) [X = llvm::Function, Y = llvm::GlobalValue]: Assertion
`isa<X>(Val) && "cast<Ty>() argument of incompatible type!"' failed.
Quuxplusone commented 9 years ago 
The current llvm-as-fuzzer.cpp leaks a bit of memory every time
llvm::report_fatal_error is called:

Direct leak of 76 byte(s) in 1 object(s) allocated from:
    #0 0x4d978b in operator new(unsigned long) /usr/local/google/home/kcc/llvm/projects/compiler-rt/lib/asan/asan_new_delete.cc:62:35
    #1 0x7f079bda8668 in __gnu_cxx::new_allocator<char>::allocate(unsigned long, void const*) /usr/local/google/home/kcc/tmp/gcc-4.8.2/build/x86_64-unknown-linux-gnu/libstdc++-v3/include/ext/new_»
    #2 0x7f079bda8668 in std::string::_Rep::_S_create(unsigned long, unsigned long, std::allocator<char> const&) /usr/local/google/home/kcc/tmp/gcc-4.8.2/build/x86_64-unknown-linux-gnu/libstdc++-»
    #3 0xc70021 in llvm::report_fatal_error(llvm::Twine const&, bool) /usr/local/google/home/kcc/llvm/lib/Support/ErrorHandling.cpp:85:26
    #4 0xc6fdd5 in llvm::report_fatal_error(char const*, bool) /usr/local/google/home/kcc/llvm/lib/Support/ErrorHandling.cpp:62:3
    #5 0xb48101 in llvm::DataLayout::parseSpecifier(llvm::StringRef) /usr/local/google/home/kcc/llvm/lib/IR/DataLayout.cpp:330:11
...

This is because the code in llvm::report_fatal_error calls this:
    handler(handlerData, Reason.str(), GenCrashDiag);

void MyFatalErrorHandler(void *user_data, const std::string& reason,
                         bool gen_crash_diag) {

We create a string object and the long-jump over it's DTOR.

This is not a blocker at this point -- we can always restart the process after
processing e.g. 100M units w/o losing much speed, but ideally we need to fix
this.
Quuxplusone commented 9 years ago

With max_len=512 I start seeing more interesting things, like bug 24661

Quuxplusone commented 9 years ago 
After a night of fuzzing I've got ~15 assertion unique failures:

llvm/include/llvm/IR/DebugInfoMetadata.h:60:
llvm::TypedDINodeRef<llvm::DIType>::TypedDINodeRef(const llvm::Metadata *) [T =
llvm::DIType]: Assertion `(!MD || isa<MDString>(MD) || isa<T>(MD)) && "Expected
valid ref"' failed.
llvm/include/llvm/IR/Instructions.h:1099: void llvm::ICmpInst::AssertOK():
Assertion `getOperand(0)->getType() == getOperand(1)->getType() && "Both
operands to ICmp instruction are not of the same type!"' failed.
llvm/include/llvm/IR/Metadata.h:938: const llvm::MDOperand
&llvm::MDNode::getOperand(unsigned int) const: Assertion `I < NumOperands &&
"Out of range"' failed.
llvm/include/llvm/IR/Type.h:97: void llvm::Type::setSubclassData(unsigned int):
Assertion `getSubclassData() == val && "Subclass data too large for field"'
failed.
llvm/include/llvm/Support/Casting.h:237: typename cast_retty<X, Y *>::ret_type
llvm::cast(Y *) [X = llvm::DICompileUnit, Y = llvm::MDNode]: Assertion
`isa<X>(Val) && "cast<Ty>() argument of incompatible type!"' failed.
llvm/include/llvm/Support/Casting.h:237: typename cast_retty<X, Y *>::ret_type
llvm::cast(Y *) [X = llvm::Function, Y = llvm::Constant]: Assertion
`isa<X>(Val) && "cast<Ty>() argument of incompatible type!"' failed.
llvm/include/llvm/Support/Casting.h:237: typename cast_retty<X, Y *>::ret_type
llvm::cast(Y *) [X = llvm::Function, Y = llvm::GlobalValue]: Assertion
`isa<X>(Val) && "cast<Ty>() argument of incompatible type!"' failed.
llvm/include/llvm/Support/Casting.h:251: typename
std::enable_if<!is_simple_type<Y>::value, typename cast_retty<X, const
Y>::ret_type>::type llvm::cast_or_null(const Y &) [X = llvm::DIType, Y =
llvm::MDOperand]: Assertion `isa<X>(Val) && "cast_or_null<Ty>() argument of
incompatible type!"' failed.
llvm/include/llvm/Support/Casting.h:269: typename cast_retty<X, Y *>::ret_type
llvm::cast_or_null(Y *) [X = llvm::MDTuple, Y = llvm::Metadata]: Assertion
`isa<X>(Val) && "cast_or_null<Ty>() argument of incompatible type!"' failed.
llvm/lib/IR/Attributes.cpp:1210: llvm::AttrBuilder
&llvm::AttrBuilder::addAlignmentAttr(unsigned int): Assertion
`isPowerOf2_32(Align) && "Alignment must be a power of two."' failed.
llvm/lib/IR/Attributes.cpp:833: llvm::AttributeSet
llvm::AttributeSet::removeAttributes(llvm::LLVMContext &, unsigned int,
llvm::AttributeSet) const: Assertion `!Attrs.hasAttribute(Index,
Attribute::Alignment) && "Attempt to change alignment!"' failed.
llvm/lib/IR/ConstantRange.cpp:49:
llvm::ConstantRange::ConstantRange(APIntMoveTy, APIntMoveTy): Assertion `(Lower
!= Upper || (Lower.isMaxValue() || Lower.isMinValue())) && "Lower == Upper, but
they aren't min or max value!"' failed.
llvm/lib/IR/Globals.cpp:209: void
llvm::GlobalVariable::setInitializer(llvm::Constant *): Assertion `InitVal-
>getType() == getType()->getElementType() && "Initializer type must match
GlobalVariable type"' failed.
llvm/lib/IR/Value.cpp:60: llvm::Value::Value(llvm::Type *, unsigned int):
Assertion `(VTy->isFirstClassType() || VTy->isVoidTy()) && "Cannot create non-
first-class values except for constants!"' failed.
llvm/lib/IR/ValueTypes.cpp:184: llvm::Type
*llvm::EVT::getTypeForEVT(llvm::LLVMContext &) const: Assertion `isExtended()
&& "Type is not extended!"' failed.
Quuxplusone commented 9 years ago

Attached repros.txt (5658 bytes, text/plain): base64-encoded reproducers

Quuxplusone commented 9 years ago 
I've added a dictionary mode to libFuzzer, similar to that in AFL.
http://llvm.org/docs/LibFuzzer.html#dictionaries
Once we get all currently known bugs in llvm-as fixed we may try that
big hummer too.
Quuxplusone commented 9 years ago 
There is a problem with the current llvm-as-fuzzer -- it accumulates some
global state and as the result it finds multiple irrelevant (parasitic)
inputs every time it runs.

One part of the problem is that we use the global context.
It's easy to fix (by creating a new context for every unit),
but it does not seem to fix the problem completely.
Investigating.
Quuxplusone commented 9 years ago

Attached llvm-as-parasitic-coverage-repro.patch (1817 bytes, text/plain): parasitic-coverage-repro

Quuxplusone commented 8 years ago 
r248556 effectively disables llvm-as-fuzzer on the fuzzer bot because
a) there are too many known crashes that need to be fixed first,
 and
b) too much garbage inputs are created due to parasitic coverage (see #10 and
#11)

Karl, I wonder if you have time to work on b)?
Quuxplusone commented 8 years ago 
(In reply to comment #12)
> r248556 effectively disables llvm-as-fuzzer on the fuzzer bot because
> a) there are too many known crashes that need to be fixed first,
>  and
> b) too much garbage inputs are created due to parasitic coverage (see #10
> and #11)
>
> Karl, I wonder if you have time to work on b)?

I'll look into both, and will focus on the parasitic coverage.
Quuxplusone commented 8 years ago

I believe the problem is due to a FoldingSet used to hold intrinsic functions. A folding set is a hashtable implemented on a SmallVector, using intrusive links to define the list of elements in a bucket.

Every time a function (declaration/definition) is parsed, a lookup is done (in the create method), it either returns a pointer (in the hashtable) to the corresponding definition, or it creates a spot for a new one, and returns the corresponding pointer so that it can be initialized.

When parsing is done, the table is cleared (but not resized). Hence, on the second parse, the table need not be increased since the first parse caused it to grow.

This explains the first growth, found in comment #11, but doesn't for the second. Still looking into this.

Quuxplusone commented 8 years ago

I looked at the parasitic growth in comment #11 some more. I'm convinced that the problem is that the "type signature" is encoded as part of the key in the folding set, and the "type signature" is a pointer to a type (which have been uniqued). This uniquifying of types happens on each iteration, using heap allocated elements. As a result, different iterations will have different hash values, which will cause collisions to randomly occur. As a result, the bucket lists change between iterations.

I don't see a way to get rid of this effect. It is ingrained in the guts of LLVM to use dynamically allocated type addresses to uniquely identify types.

Quuxplusone commented 8 years ago 
> I don't see a way to get rid of this effect. It is ingrained in the guts of
> LLVM to use dynamically allocated type addresses to uniquely identify types.

I am ignorant about this part of LLVM: can you point to the exact code &
objects?
Are these objects a real global state, or they are part of LLVM context?
Quuxplusone commented 8 years ago 
Its in the LLVMContext (I think).

When constructor Function::Function() is called, somehow field IntID is set,
and this value then causes a lookup. It then calls lookupIntrinsicID (in
function.cpp). This lookup then looks up (in some table) that is a folding set
for the intrinsic.  This table has entries that contain other things than just
intrinsics. The elements are VERY generic in FoldingSet, and all I know is that
other elements vary on contents between iterations.

I'm guessing this is some sort of symbol table, and I'm guessing that these
other entries have types. However, I haven't convinced myself of that because:

1) I really don't know what folding set I am in.
2) The generic nodeequals doesn't match these elements, and just skips over
them.
3) The elements that are skipped I haven't figured out where they are added.

BTW, it is very hard to figure out what is going on because much of the driving
code is automatically generated code, and the abstractions are totally gone
when you look at the low-level code that is actually being run in the debugger.
Quuxplusone commented 8 years ago 
I looked a bit deeper, and I think the cause of the problem is due to the
uniquifying of "attribute sets". The method AttributeSetNode::get(LLVMContext
&C, ArrayRef<Attribute> Attrs) looks for the attribute set in C.pImpl to see if
the attribute set is already defined. If it is found, it returns the existing,
Otherwise it creates a new (heap allocated) AttributeSetNode.

The problem is how nodes are "profiled" (i.e. the Profile method used to
compute the hash on the unique bits of the data). The class AttributeSetImpl
defines Profile in terms of method getNode, which returns a pair<unsigned,
AttributeSetNode *> for each element. The ID is computed by adding these two
values using ID.addInteger() and ID.addPointer().

If you look up the definition of method FoldingSetNodeID::AddPointer(const
void* Ptr) it simply adds the pointer to the sequence of bits in the Node ID.

Hence, depending on dynamic allocation, you will get different hash values.
This explains why we get different hash tables on different iterations.