Fix 'has_new_bits' function

wakolzin commented 4 years ago

In function 'has_new_bits' were fixed following points:

new hit counts bucket detection;
virgin bits update.

Let's consider the following case. Before another program start we have: virgin_map[100] = 0xff // '100' is chosen just for example Let's say after run we have: trace_bits[100] = 0xff // > 128, i.e. we got into 7th hit counts bucket (128+) After 'has_new_bits' was called: virgin_map[100] = 0x00 and we will not ever detect any bucket, despite we hit in only one bucket during all program runs.

In fact, we must update virgin_map so as: virgin_map[100] = 0x8f It is somewhat extreme example, but current 'has_new_bits' realization causes loss of some new testcases (following new path criterion from white paper) and in some cases it causes save extra entries in queue (such cases were not considered here).

And that is a fix.

googlebot commented 4 years ago

Thanks for your pull request. It looks like this may be your first contribution to a Google open source project (if not, look below for help). Before we can look at your pull request, you'll need to sign a Contributor License Agreement (CLA).

:memo: Please visit https://cla.developers.google.com/ to sign.

Once you've signed (or fixed any issues), please reply here with @googlebot I signed it! and we'll verify it.

What to do if you already signed the CLA

Individual signers

It's possible we don't have your GitHub username or you're using a different email address on your commit. Check your existing CLA data and verify that your email is set on your git commits.

Corporate signers

Your company has a Point of Contact who decides which employees are authorized to participate. Ask your POC to be added to the group of authorized contributors. If you don't know who your Point of Contact is, direct the Google project maintainer to go/cla#troubleshoot (Public version).
The email used to register you as an authorized contributor must be the email used for the Git commit. Check your existing CLA data and verify that your email is set on your git commits.
The email used to register you as an authorized contributor must also be attached to your GitHub account.

ℹ️ Googlers: Go here for more info.

googlebot commented 4 years ago

Thanks for your pull request. It looks like this may be your first contribution to a Google open source project (if not, look below for help). Before we can look at your pull request, you'll need to sign a Contributor License Agreement (CLA).

:memo: Please visit https://cla.developers.google.com/ to sign.

Once you've signed (or fixed any issues), please reply here with @googlebot I signed it! and we'll verify it.

What to do if you already signed the CLA

Individual signers

It's possible we don't have your GitHub username or you're using a different email address on your commit. Check your existing CLA data and verify that your email is set on your git commits.

Corporate signers

Your company has a Point of Contact who decides which employees are authorized to participate. Ask your POC to be added to the group of authorized contributors. If you don't know who your Point of Contact is, direct the Google project maintainer to go/cla#troubleshoot (Public version).
The email used to register you as an authorized contributor must be the email used for the Git commit. Check your existing CLA data and verify that your email is set on your git commits.
The email used to register you as an authorized contributor must also be attached to your GitHub account.

ℹ️ Googlers: Go here for more info.

wakolzin commented 4 years ago

@googlebot I signed it!

googlebot commented 4 years ago

CLAs look good, thanks!

ℹ️ Googlers: Go here for more info.

googlebot commented 4 years ago

CLAs look good, thanks!

ℹ️ Googlers: Go here for more info.

vanhauser-thc commented 4 years ago

I would not call it a fix as it is behaving as designed.

And I am not sure about your analysis. in run_target() after the execution classify_counts() is called, and that normalizes each byte entry to the highest bit only. hence a trace_bit[100] = 255 value will be reduces to 128 and therefore leave 7 bits set in virgin_bits.

following new path criterion from white paper

what is this?

wakolzin commented 4 years ago

@vanhauser-thc Yes, I agree. It was my inattention. By "new path criterion" i meant new edge or new backet detection.

vanhauser-thc commented 4 years ago

@vanhauser-thc Yes, I agree. It was my inattention. By "new path criterion" i meant new edge or new backet detection.

I meant the whitepaper you were refering to :)

wakolzin commented 4 years ago

@vanhauser-thc https://lcamtuf.coredump.cx/afl/technical_details.txt

2) Detecting new behaviors

wakolzin commented 4 years ago

@vanhauser-thc Thanks for review. I close pull request.

google / AFL