Implement Expression Rewriting.

feliam commented 6 years ago

KLEE. Implement the most basic optimizations like the ones yo can find in a compiler: e.g., simple arithmetic simplifications (x + 0 = x), strength reduction (x 2n = x << n), linear simplification (2x - x = x), etc.

There is some optimizations already implemented here: https://github.com/trailofbits/manticore/blob/98190d891d87ac2f3ec3ba5927e6fd4b024cc7e2/manticore/core/smtlib/visitors.py#L351

To consider this issue fixed we need to: 1) Find a good and exhaustive list of common expression simplifications as the ones found in compilers. 2) Implement the rewriting visitors for all of the simplifications using the ones already implemented as inspirational guide. 3) Document each transformation. 4) Add tests for each. Ask the solver to demonstrate the simplified expression is equivalent to the original one. 5) Be sure the taint of expressions is maintained in the simplification if required. 6) This should be configurable using config.py 7) Overall symbolic execution performance gain should be measure/tested over a big test set (see https://github.com/trailofbits/manticore/issues/1204)

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

This issue now has a funding of 100.0 DAI (100.0 USD @ $1.0/DAI) attached to it as part of the ECF fund.

If you would like to work on this issue you can 'start work' on the Gitcoin Issue Details page.
- Want to chip in? Add your own contribution here.
- Questions? Checkout Gitcoin Help or the Gitcoin Slack
- $56,100.13 more funded OSS Work available on the Gitcoin Issue Explorer

aj07 commented 5 years ago

@feliam need your confirmation before to start work on this bounty

feliam commented 5 years ago

Hi! @aj07 I'm exited you want to start this. \o/ Be prepared you'll be approved soon.

mkosowsk commented 5 years ago

@aj07 you have been approved to start work, please start at your earliest convenience. Thanks!

gitcoinbot commented 5 years ago

@aj07 Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

[x] reminder (3 days)
[ ] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

aj07 commented 5 years ago

@gitcoinbot yes working on it

gitcoinbot commented 5 years ago

@aj07 Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

[x] reminder (3 days)
[ ] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

@aj07 Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

[x] reminder (3 days)
[ ] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

@aj07 due to inactivity, we have escalated this issue to Gitcoin's moderation team. Let us know if you believe this has been done in error!

[x] reminder (3 days)
[x] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

@aj07 due to inactivity, we have escalated this issue to Gitcoin's moderation team. Let us know if you believe this has been done in error!

[x] reminder (3 days)
[x] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

aj07 commented 5 years ago

@gitcoinbot it took some time to understand it. Give me 1 week more. It will be done

gitcoinbot commented 5 years ago

@aj07 Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

[x] reminder (3 days)
[ ] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

@aj07 Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

[x] reminder (3 days)
[ ] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

@aj07 due to inactivity, we have escalated this issue to Gitcoin's moderation team. Let us know if you believe this has been done in error!

[x] reminder (3 days)
[x] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

aj07 commented 5 years ago

@feliam correct me if I am wrong. We need to Implement the basic optimizations mirror or we need to do the things mentioned in todo list?

gitcoinbot commented 5 years ago

@aj07 Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

[x] reminder (3 days)
[ ] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

@aj07 Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

[x] reminder (3 days)
[ ] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

@aj07 due to inactivity, we have escalated this issue to Gitcoin's moderation team. Let us know if you believe this has been done in error!

[x] reminder (3 days)
[x] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

rmshea commented 5 years ago

hey @feliam, ryan from gitcoin here. do you think you could take a look at @aj07's questions? thanks! 😄

feliam commented 5 years ago

@aj07 the idea is to implement the full set of the most common expression optimizations. (cc ryan-shea)

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

@aj07 due to inactivity, we have escalated this issue to Gitcoin's moderation team. Let us know if you believe this has been done in error!

[x] reminder (3 days)
[x] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

aj07 commented 5 years ago

@feliam any feedback?

gitcoinbot commented 5 years ago

@aj07 Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

[x] reminder (3 days)
[ ] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 2 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

Workers have applied to start work.

These users each claimed they can complete the work by 3 years, 3 months ago. Please review their action plans below:

1) pykagamers has applied to start work _(Funders only: approve worker | reject worker)_.

Me gustaría poder trabajar y aprender un poco acerca de sus protocolos de trabajo

Learn more on the Gitcoin Issue Details page.

trailofbits / manticore

Implement Expression Rewriting. #1199