[wasm] improve handling of malformed input

[wasm] improve handling of malformed inputs

When reading malformed input, the length of variable-length types can be very large. Computing operand length with this and adding it to PC will overflow and screw up decode.

This patch switches to unsigned int for arity and lengths, terminates loop analysis on error, adds overflow checking to BranchTableOperand, and adds a unit test.

Committed: https://crrev.com/fd2bf837a536827ea697a4a4de970886a4c288bc
Cr-Commit-Position: refs/heads/master@{#37301}

[ddchen, 2016-06-09 02:33:22]

ddchen@chromium.org changed reviewers:
+ bradnelson@chromium.org, jfb@chromium.org, titzer@chromium.org

[ddchen, 2016-06-09 02:33:23]

AFL generated a test case
(https://drive.google.com/a/google.com/file/d/0B8HhUsNH3jEnbTF5RTRLc3pJWE0/vie...)
that crashes V8 in debug mode. The input is a malformed WebAssembly file with a
main function that contains a block, a loop, a 64-bit floating-point negation,
and garbage.

During parsing, V8 will call ast-decoder.cc:AnalyzeLoopAssignment(), which uses
the opcode length to advance current PC pointer. After encountering the negation
instruction, there are two bugs. (1) A stack-based parser will recognize that
the expression stack is empty, and abort. However, the current parser does not,
and will continue until it reaches the end of the function body. Currently, the
parser interprets the first part of the garbage as a branch table, and advances
the PC by the opcode length. (2) The second bug is that many offsets and length
variables in the code are represented as signed integers, instead of size_t,
ptrdiff_t, or otherwise appropriate. As a result, when the parser reads a
variable-length integer, the length variable can become negative and  set the PC
to less than the start of the function body.

This patch fixes (2), which allows the parser to recognize that a large positive
offset is out of bounds. But, it does not fix (1), since smaller values  will
not exceed the bound check.

To reproduce: 
./out/x64.debug/d8 --expose-wasm
binaryen/test/wasm-install/wasm-install/lib/wasm.js --
id\:000000\,sig\:11\,src\:000272\,op\:flip32\,pos\:128

[titzer, 2016-06-09 06:48:15]

Looks mostly good.

Can you please add a unit test or cctest for the bug you are fixing?

https://codereview.chromium.org/2052623003/diff/20001/src/wasm/ast-decoder.h
File src/wasm/ast-decoder.h (right):

https://codereview.chromium.org/2052623003/diff/20001/src/wasm/ast-decoder.h#...
src/wasm/ast-decoder.h:28: unsigned int length;
You can just use "unsigned", which is short for "unsigned int".

[titzer, 2016-06-09 06:50:00]

On 2016/06/09 02:33:23, ddchen wrote:
> AFL generated a test case
>
(https://drive.google.com/a/google.com/file/d/0B8HhUsNH3jEnbTF5RTRLc3pJWE0/vie...)
> that crashes V8 in debug mode. The input is a malformed WebAssembly file with
a
> main function that contains a block, a loop, a 64-bit floating-point negation,
> and garbage.
> 
> During parsing, V8 will call ast-decoder.cc:AnalyzeLoopAssignment(), which
uses
> the opcode length to advance current PC pointer. After encountering the
negation
> instruction, there are two bugs. (1) A stack-based parser will recognize that
> the expression stack is empty, and abort. However, the current parser does
not,
> and will continue until it reaches the end of the function body. Currently,
the
> parser interprets the first part of the garbage as a branch table, and
advances
> the PC by the opcode length. (2) The second bug is that many offsets and
length
> variables in the code are represented as signed integers, instead of size_t,
> ptrdiff_t, or otherwise appropriate. As a result, when the parser reads a
> variable-length integer, the length variable can become negative and  set the
PC
> to less than the start of the function body.

Can't this also happen with wraparound? E.g. if the length becomes a very large
positive number, then the pc could wrap around and then be less than start
(again).

> 
> This patch fixes (2), which allows the parser to recognize that a large
positive
> offset is out of bounds. But, it does not fix (1), since smaller values  will
> not exceed the bound check.
> 
> To reproduce: 
> ./out/x64.debug/d8 --expose-wasm
> binaryen/test/wasm-install/wasm-install/lib/wasm.js --
> id\:000000\,sig\:11\,src\:000272\,op\:flip32\,pos\:128

[ddchen, 2016-06-09 19:25:39]

Yes, that is still a problem. This patch makes things a little better, but the
root cause is still in the parser and with integer overflow. I can file a
tracking bug for the parser separately?

I made a mistake in the description above; the actual bug is what you just
described. In the statement "length = len1 + len2 + (table_count + 1) *
sizeof(uint32_t)" for v8::internal::wasm::BranchTableOperand, signed overflow is
occurring, which is undefined behavior in C++. Changing to unsigned improves on
this aspect, since unsigned overflow is defined, but overflow is still
occurring.

In patch set #3, I modified the loop assignment to terminate and return NULL if
a decode error is encountered. This made it easier to implement a unit test. Not
sure if this portion should be a separate CL?

jochen: jfb suggested using safe_math may be better?

[titzer, 2016-06-10 07:40:00]

https://codereview.chromium.org/2052623003/diff/40001/src/wasm/ast-decoder.cc
File src/wasm/ast-decoder.cc (right):

https://codereview.chromium.org/2052623003/diff/40001/src/wasm/ast-decoder.cc...
src/wasm/ast-decoder.cc:1468: return (limit_ != start_) ? assigned : NULL;
You can just use ok().

[titzer, 2016-06-10 07:40:53]

On 2016/06/09 19:25:39, ddchen wrote:
> Yes, that is still a problem. This patch makes things a little better, but the
> root cause is still in the parser and with integer overflow. I can file a
> tracking bug for the parser separately?
> 
> I made a mistake in the description above; the actual bug is what you just
> described. In the statement "length = len1 + len2 + (table_count + 1) *
> sizeof(uint32_t)" for v8::internal::wasm::BranchTableOperand, signed overflow
is
> occurring, which is undefined behavior in C++. Changing to unsigned improves
on
> this aspect, since unsigned overflow is defined, but overflow is still
> occurring.
> 

We should check for overflow in BranchTableOperand.

> In patch set #3, I modified the loop assignment to terminate and return NULL
if
> a decode error is encountered. This made it easier to implement a unit test.
Not
> sure if this portion should be a separate CL?
> 

Yes, please add the unittest in this CL.

> jochen: jfb suggested using safe_math may be better?

Seems like overkill in this situation.

[ddchen, 2016-06-10 19:27:37]

Description was changed from

==========
[wasm] use unsigned int for arity and lengths

When reading malformed input, the length of variable-length types
can become negative. Computing operand length with this and adding
it to pc will screw up decode.
==========

to

==========
[wasm] improve handling of malformed inputs

When reading malformed input, the length of variable-length types can be very
large. Computing operand length with this and adding it to PC will overflow and
screw up decode.
    
This patch switches to unsigned int for arity and lengths, terminates loop
analysis on error, adds overflow checking to BranchTableOperand, and adds a unit
test.
==========

[ddchen, 2016-06-10 20:39:10]

I added the overflow check, the unit test was in the previous patch set.

[bradnelson, 2016-06-24 18:40:47]

the int -> unsigned thing here is reminding me we need a larger team discussion
around sizes signedness and things like safe_math. But that's separate.

https://codereview.chromium.org/2052623003/diff/60001/src/wasm/ast-decoder.cc
File src/wasm/ast-decoder.cc (right):

https://codereview.chromium.org/2052623003/diff/60001/src/wasm/ast-decoder.cc...
src/wasm/ast-decoder.cc:1468: return ok() ? assigned : NULL;
nullptr

https://codereview.chromium.org/2052623003/diff/60001/src/wasm/ast-decoder.h
File src/wasm/ast-decoder.h (right):

https://codereview.chromium.org/2052623003/diff/60001/src/wasm/ast-decoder.h#...
src/wasm/ast-decoder.h:164: CHECK(table_count <= (UINT_MAX / sizeof(uint32_t)) -
1);
I believe by check, Ben meant invoke error on overflow.

[ddchen, 2016-06-24 21:10:21]

On 2016/06/24 18:40:47, bradnelson wrote:
> the int -> unsigned thing here is reminding me we need a larger team
discussion
> around sizes signedness and things like safe_math. But that's separate.
> 
> https://codereview.chromium.org/2052623003/diff/60001/src/wasm/ast-decoder.cc
> File src/wasm/ast-decoder.cc (right):
> 
>
https://codereview.chromium.org/2052623003/diff/60001/src/wasm/ast-decoder.cc...
> src/wasm/ast-decoder.cc:1468: return ok() ? assigned : NULL;
> nullptr
> 
> https://codereview.chromium.org/2052623003/diff/60001/src/wasm/ast-decoder.h
> File src/wasm/ast-decoder.h (right):
> 
>
https://codereview.chromium.org/2052623003/diff/60001/src/wasm/ast-decoder.h#...
> src/wasm/ast-decoder.h:164: CHECK(table_count <= (UINT_MAX / sizeof(uint32_t))
-
> 1);
> I believe by check, Ben meant invoke error on overflow.

Fixed in the latest patchset.

[bradnelson, 2016-06-27 05:00:02]

The CQ bit was checked by bradnelson@chromium.org

[bradnelson, 2016-06-27 05:00:03]

lgtm

[commit-bot: I haz the power, 2016-06-27 05:00:10]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-06-27 05:01:26]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-06-27 05:01:27]

Try jobs failed on following builders:
  v8_android_arm_compile_rel on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_android_arm_compile_rel/...)
  v8_linux64_asan_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_asan_rel_ng/buil...)
  v8_linux64_avx2_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_avx2_rel_ng/buil...)
  v8_linux64_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux64_rel_ng/builds/7941)
  v8_linux_arm_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_arm_rel_ng/builds/...)
  v8_linux_dbg_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_dbg_ng/builds/7927)
  v8_linux_mips64el_compile_rel on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_mips64el_compile_r...)
  v8_linux_mipsel_compile_rel on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_mipsel_compile_rel...)
  v8_linux_nodcheck_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_linux_nodcheck_rel_ng/bu...)
  v8_mac_rel_ng on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_mac_rel_ng/builds/3847)
  v8_presubmit on master.tryserver.v8 (JOB_FAILED,
http://build.chromium.org/p/tryserver.v8/builders/v8_presubmit/builds/18026)

[bradn, 2016-06-27 05:58:48]

bradnelson@google.com changed reviewers:
+ bradnelson@google.com

[bradn, 2016-06-27 05:58:49]

Looks like you need a merge.

[ddchen, 2016-06-27 17:21:18]

The CQ bit was checked by ddchen@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-06-27 17:21:25]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-06-27 18:03:49]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-06-27 18:03:51]

Dry run: This issue passed the CQ dry run.

[ddchen, 2016-06-27 20:33:26]

The CQ bit was checked by ddchen@chromium.org

[ddchen, 2016-06-27 20:33:27]

The patchset sent to the CQ was uploaded after l-g-t-m from
bradnelson@chromium.org
Link to the patchset: https://codereview.chromium.org/2052623003/#ps100001
(title: "rebase")

[commit-bot: I haz the power, 2016-06-27 20:33:34]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-06-27 20:35:39]

Description was changed from

==========
[wasm] improve handling of malformed inputs

When reading malformed input, the length of variable-length types can be very
large. Computing operand length with this and adding it to PC will overflow and
screw up decode.
    
This patch switches to unsigned int for arity and lengths, terminates loop
analysis on error, adds overflow checking to BranchTableOperand, and adds a unit
test.
==========

to

==========
[wasm] improve handling of malformed inputs

When reading malformed input, the length of variable-length types can be very
large. Computing operand length with this and adding it to PC will overflow and
screw up decode.
    
This patch switches to unsigned int for arity and lengths, terminates loop
analysis on error, adds overflow checking to BranchTableOperand, and adds a unit
test.
==========

[commit-bot: I haz the power, 2016-06-27 20:35:40]

Committed patchset #6 (id:100001)

[commit-bot: I haz the power, 2016-06-27 20:37:38]

Description was changed from

==========
[wasm] improve handling of malformed inputs

When reading malformed input, the length of variable-length types can be very
large. Computing operand length with this and adding it to PC will overflow and
screw up decode.
    
This patch switches to unsigned int for arity and lengths, terminates loop
analysis on error, adds overflow checking to BranchTableOperand, and adds a unit
test.
==========

to

==========
[wasm] improve handling of malformed inputs

When reading malformed input, the length of variable-length types can be very
large. Computing operand length with this and adding it to PC will overflow and
screw up decode.

This patch switches to unsigned int for arity and lengths, terminates loop
analysis on error, adds overflow checking to BranchTableOperand, and adds a unit
test.

Committed: https://crrev.com/fd2bf837a536827ea697a4a4de970886a4c288bc
Cr-Commit-Position: refs/heads/master@{#37301}
==========

[commit-bot: I haz the power, 2016-06-27 20:37:40]

Patchset 6 (id:??) landed as
https://crrev.com/fd2bf837a536827ea697a4a4de970886a4c288bc
Cr-Commit-Position: refs/heads/master@{#37301}