Closed Bug 519873 Opened 11 years ago Closed 10 years ago

NJ merge: lirasm --random mode

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED

People

(Reporter: graydon, Assigned: njn)

References

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(1 file, 3 obsolete files)

Back in the bad old days of "shaking out LIR buffer-linking bugs" last winter, I had a patch I was using to lirasm that synthetically fuzzed the compilation pipeline with random instructions. It had a holding buffer full of live operands and then randomly added new operands to the fragment built from existing, randomly-chosen live ones, retiring them as the holding buffer got too big. 

This was pretty simplistic and heavy-handed, but it turns out to be a handy way of catching memory errors. I'd like to revive this notion in the nanojit-central repository. We're too under-powered in testsuites there at the moment; a valgrinded --random mode will make a good smoketest on whatever tinderbox we eventually get to monitor the new repository.

Attached is a completely bit-rotted patch that nonetheless shows the idea. But feel free to write from scratch, with a more elegant structure driving the code synthesis. Probably it'd benefit from some richer classes or helper functions that can be used to set up random-but-parameterized patterns of code.

Such helpers might also be applicable to the problem of writing a self-benchmarking --stress mode for lirasm, which I'll open another bug to track.
Attached patch work-in-progress (obsolete) — Splinter Review
I resurrected the patch and made a couple of improvements:

- It no longer generates 1--10 of a particular instruction kind (load/store/imm/ALU) in a row -- that was confusing and lead to very unrealistic code.

- I've biased immediates to smaller values, which reflects what real code does and will stress CseFilter more realistically.

A couple of things I'm unsure about the original patch:

- Loads and stores were done to/from random offsets of the 'state' variable, called 'base' in the patch.  This was weird and, in the store case, caused crashes.  Not surprising, since it was basically writing memory at random.  I'm not sure how this was ever supposed to work.  I've disabled store generation for the moment, maybe allocating some stack space with LIR_alloc would be better.  Or even just malloc'ing some space from within lirasm.

- We don't have to worry about the outOMem case thanks to the new allocators, right?
Attachment #403921 - Attachment is obsolete: true
(In reply to comment #1)
> Created an attachment (id=403967) [details]
> work-in-progress
> 
> - Loads and stores were done to/from random offsets of the 'state' variable,
> called 'base' in the patch.  This was weird and, in the store case, caused
> crashes.  Not surprising, since it was basically writing memory at random.  I'm
> not sure how this was ever supposed to work.  I've disabled store generation
> for the moment, maybe allocating some stack space with LIR_alloc would be
> better.  Or even just malloc'ing some space from within lirasm.

And I changed loads to be from a small region around the 'base' pointer.

Also, any reason why random() was used in some places and rand() in others?
(In reply to comment #1)

> A couple of things I'm unsure about the original patch:
> 
> - Loads and stores were done to/from random offsets of the 'state' variable,
> called 'base' in the patch.  This was weird and, in the store case, caused
> crashes.  Not surprising, since it was basically writing memory at random.  I'm
> not sure how this was ever supposed to work.  I've disabled store generation
> for the moment, maybe allocating some stack space with LIR_alloc would be
> better.  Or even just malloc'ing some space from within lirasm.

There wasn't an --execute mode for lirasm when I wrote it the first time. So it didn't need to run :)

> - We don't have to worry about the outOMem case thanks to the new allocators,
> right?

Yes.
(In reply to comment #2)

> Also, any reason why random() was used in some places and rand() in others?

Good question, I have no idea. Probably typo.
Attached patch patch (obsolete) — Splinter Review
This patch implements --random, based on Graydon's patch.  

Basics:
- It just generates a single block.
- The block length is controllable by the optional argument to --random, 
  the default is 100.
- Only loads, stores, immediates, and binary ALU operations are generated.
- Loads and stores are to a small scratch space on the stack.

Attempts at realism:
- There is weighting of instruction classes, so that opcode frequency is 
  adjustable and roughly reflects real code.
- There is also weighting of immediate generation, so small values (esp 0 
  and 1) are more common.
- The remaining shortcomings (of which there are many) are documented.

Other Improvements not directly related to --random:
- With -v, it now prints regalloc and activation info along with the
  assembly info, because it's useful.
- I beefed up the option processing.  The previous processing was only 
  suitable for options without arguments.
- I added a decent usage message.
- I allowed you to specify -v without --execute, because it can be useful.

It runs Valgrind-clean.

There's obviously a lot of scope for improving this, but I think this is a 
good enough starting point for this bug.  Graydon, what's the plan for 
committing this -- will it go in after the NJ merge is complete?

An interesting point w.r.t. the suggested --stress option -- currently it
runs out of stack space if you do a block length of much more than 10,000, 
due to spilling of 64-bit immediates.  The spill area is only 1024 bytes, we
may want to increase that.
Attachment #403967 - Attachment is obsolete: true
Attachment #404203 - Flags: review?(jorendorff)
Thanks, this is a lot like what I was thinking. Your comment-block explaining the caveats is also helpful for planning further work. Feel free to file each of those caveats as enhancement bugs on lirasm and take them or assign them to me or whatever. The more depth fuzzing can be made to probe, the better.
After reading some stuff that Jesse wrote about fuzzing, I think this --random mode is a bit different to typical fuzzers.  It's because we're constructing the random code via an internal API.  We could easily choose to generate bogus LIR code that will crash the compiler (eg. create a LIR_add instruction with bogus operands) but that won't tell us anything because it didn't originate at the user-level.

In other words, Jesse wrote about the need to balance valid input with invalid input, but in this case, I can't see how invalid input can be involved.  We could fuzz the text input to the assembler but that doesn't seem worthwhile because the assembler isn't a tool used by users.

I can imagine that the --random mode was useful earlier in the year when skips were still used and the LIR representation was more complex (with tramps, etc) and so just throwing lots of code at the compiler had a chance of finding bugs.  But now that LIR is simpler and more robust, I wonder how many bugs --random will find.  I guess it could find some via legal-but-rare code sequences.
Hm. Well, I agree that from a security perspective, probing illegal sequences to check that they're properly rejected is probably at least as valuable as the opposite, because you are talking about an attacker who can send any single byte. No point fuzzing legal SQL when you have an input routine that doesn't handle escaping properly. Sure.

But: all the fuzzer bugs from Jesse's setup that I've had assigned have been exactly what you describe: legal-but-rare. Things that should work -- that the language spec *says* should work -- and actually crash, corrupt, or otherwise fail when interpreted. Usually quite deep in the interpreter.

That has been my experience with randomizers at the API level too, in other programs. There was one on one of the first major projects I worked on (sid) and I built several on monotone, and they invariably hit all the weirdest legal-but-rare cases in the API they were hooked into. Just for internal, diagnostic, non-security work (or at least, not with a specific "this input could be sent in to crash us" attack scenarios in mind; possibly you could work backwards to figure out a legal user-input). 

They also served as a pretty good encoding of what legal API usage *is*, as they aggressively explored every part they were connected to. This in turn serves as a good blanket regression test: once you've encoded "legal API surface" in a randomizer's control program, any fatal-bug-carrying commit that can be triggered from that legal API surface has good odds of being tickled.

But .. I can't make any more concrete claim than that; it's like saying "having static types has helped me in the past", it's a matter of comfort and faith. Maybe I am seeing what I want to see. If you're not interested in doing further work on it, that's ok, I will carry on extending it as time permits on my own.
I do think it's worth putting more effort into it, I just wanted to write down my reaction to Jesse's experiences, partly in case it was informative for others and partly in case there was aspects I was missing.  If you've had good experiences with this kind of thing then that is encouraging.
Comment on attachment 404203 [details] [diff] [review]
patch

No need to review this patch, I've greatly expanded it and will post the new version for review soon.
Attachment #404203 - Flags: review?(jorendorff)
Attached patch patch, v2Splinter Review
Extensions to the --random patch:

- New LIR features tested:  unary ops, 64-bit integer immediates and ops
  (qiadd, etc), qlo/qhi/qjoin, i2f/u2f, i2q/u2q, icall/fcall/qcall, div/mod,
  iaddp/qaddp, CSEable loads.

- Splits the LIns classes more finely.
  
- Now runs on X64 correctly.

- Adds LInsClasses.tbl, much like LIRopcode.tbl it allows all the
  per-class info to be in one place, which makes adding new classes much
  easier.  (Nb: I hope the copyright notice is ok, I particularly was unsure
  about the "The Original code is SpiderMonkey nanojit" part.)

- Avoids a compile warning in a lirasm.cpp sprintf() call.

- There were some "<<2" expressions used when building function _argtypes
  masks.  The width of these bit-fields changed from 2 to 3 a while back
  (the constant ARGSIZE_SHIFT is now used instead of a magic number).  I
  introduced some abstraction functions that made building _argtypes masks
  less error-prone, and used them myself for the --random stuff as well.
  These should eventually filter out to wider use (see bug 507089).

- Changes the writer pipeline initialisation to be easier to read, and
  more like that used in jstracer.cpp.  This also allows you to cut out a
  stage by just commenting out the relevant line.

- Augments testlirc.sh so it runs a test with --random 1000.


Some fixes outside of lirasm spurred by things that --random found:

- Adds punctuation to clarify a comment in NativeX64.cpp.

- Fixes two assertions in NativeX64.cpp to allow obscure legitimate cases
  that --random threw up.

- Allows more than 5-bit offsets to LD8Z in Nativei386.h;  the comment
  talked about Thumb code and so presumably was accidentally copied from the
  ARM backend or something like that.

- Allows FP as the 2nd arg in SSE_MOVDm in Nativei386.h.  This was
  necessary for qlo to work (so presumably qlo isn't tested on i386).

Nb: although assembleRandomFragment() is within class FragmentAssembler, it
uses a bunch of static functions and constants that are outside class
FragmentAssembler.  This seemed ok to me but I could move them inside the
class (even to an inner class) if it seems useful.
Attachment #404203 - Attachment is obsolete: true
Attachment #405375 - Flags: review?(graydon)
Comment on attachment 405375 [details] [diff] [review]
patch, v2

Looks great! Thanks.
Attachment #405375 - Flags: review?(graydon) → review+
http://hg.mozilla.org/mozilla-central/rev/cae6491960ee
Status: NEW → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.