php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #77720 Out of memory error when parsing yaml file can lead to DoS
Submitted: 2019-03-10 18:15 UTC Modified: 2020-05-06 04:20 UTC
From: unshorn at gmail dot com Assigned: bd808 (profile)
Status: Closed Package: yaml (PECL)
PHP Version: 7.2.16 OS: Linux
Private report: No CVE-ID: None
View Add Comment Developer Edit
Welcome! If you don't have a Git account, you can't do anything here.
You can add a comment by following this link or if you reported this bug, you can edit this bug over here.
Block user comment
Status: Assign to:
Package:
Bug Type:
Summary:
From: unshorn at gmail dot com
New email:
PHP Version: OS:

 

 [2019-03-10 18:15 UTC] unshorn at gmail dot com
Description:
------------
Out of memory error when parsing yaml file can lead to DoS

Test script:
---------------
Use yaml_parse_file and supply the file with contents from this url
https://gist.github.com/unshorn/e1d1f1c61242fdfb474641adfa0be9e9


Expected result:
----------------
PHP crashes with out of memory error 
mmap() failed: [12] Cannot allocate memory

mmap() failed: [12] Cannot allocate memory
PHP Fatal error:  Out of memory (allocated 22179676160) (tried to allocate 6823577062 bytes) 



Patches

Add a Patch

Pull Requests

Pull requests:

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2019-03-11 13:59 UTC] cmb@php.net
-Assigned To: +Assigned To: bd808
 [2020-05-03 20:43 UTC] bd808@php.net
YAML document triggering this memory exhaustion condition:

  ---
  - &a ["lol","lol","lol","lol","lol","lol","lol","lol","lol"]
  - ? &b [{*a:1},{*a:1},{*a:1},{*a:1},{*a:1},{*a:1},{*a:1},{*a:1},{*a:}] : "foo"
  - ? &c [{*b:1},{*b:1},{*b:1},{*b:1},{*b:1},{*b:1},{*b:1},{*b:1},{*b:}] : "foo"
  - ? &d [{*c:1},{*c:1},{*c:1},{*c:1},{*c:1},{*c:1},{*c:1},{*c:1},{*c:}] : "foo"
  - ? &e [{*d:1},{*d:1},{*d:1},{*d:1},{*d:1},{*d:1},{*d:1},{*d:1},{*d:}] : "foo"
  - ? &f [{*e:1},{*e:1},{*e:1},{*e:1},{*e:1},{*e:1},{*e:1},{*e:1},{*e:}] : "foo"
  - ? &g [{*f:1},{*f:1},{*f:1},{*f:1},{*f:1},{*f:1},{*f:1},{*f:1},{*f:}] : "foo"
  - ? &h [{*g:1},{*g:1},{*g:1},{*g:1},{*g:1},{*g:1},{*g:1},{*g:1},{*g:}] : "foo"
  - ? &i [{*h:1},{*h:1},{*h:1},{*h:1},{*h:1},{*h:1},{*h:1},{*h:1},{*h:}] : "foo"
  - ? &j [{*i:1},{*i:1},{*i:1},{*i:1},{*i:1},{*i:1},{*i:1},{*i:1},{*i:}] : "foo"
  - ? &k [{*j:1},{*j:1},{*j:1},{*j:1},{*j:1},{*j:1},{*j:1},{*j:1},{*j:}] : "foo"
  ...

See also: https://en.wikipedia.org/wiki/Billion_laughs_attack

Because this extension uses PHP references internally, it seems to deal with the "normal" billion laughs attack reasonably well. This particular attack takes advantage of a YAML 1.1 spec feature of questionable utility where YAML's "mapping" type (<https://yaml.org/type/map.html>) allows keys to be any valid YAML type, not limited to scalars. In order to handle this feature in PHP space, we use php_var_serialize() to create a string representation of non-scalar keys and then use that string as the key in a native PHP array. 

At some level this is a problem of parsing perverse YAML input. The memory allocation failure is actually a correct response. PHP is doing what is supposed to do by capping the amount of memory consumed based on configuration. A true DoS would be if PHP happily allowed 100% of system RAM to be exhausted rather than respecting the allowed RAM quota for a single PHP process.

One mitigation for this particular attack would be introducing a feature flag to disable non-scalar mapping keys. Disabling non-scalar keys by default would be a breaking change. That would mean either a major version bump or introducing the flag with a default value that did not prevent this exploit and then toggling to a "safe by default" in a future version.
 [2020-05-03 21:10 UTC] bd808@php.net
PyYAML seems to deal with this by raising an error while attempting to construct the native form of the mapping ("yaml.constructor.ConstructorError: while constructing a mapping [...] found unhashable key").
 [2020-05-03 21:21 UTC] stas@php.net
Would it be feasible to make YAML use PHP memory management for everything? PHP OOM is a normal condition, mmap() errors and process crashing is not.
 [2020-05-03 21:36 UTC] bd808@php.net
Native PHP 7.3 equivalent behavior for trying to use a non scalar as a key seems to be to emit a warning for "Illegal offset type" and continue processing. A PHP translation of the reported input emits 100 warnings and ultimately produces an array equivalent to `[["lol","lol","lol","lol","lol","lol","lol","lol","lol"]]`.
 [2020-05-03 21:48 UTC] bd808@php.net
> Would it be feasible to make YAML use PHP memory management for everything? PHP OOM is a normal condition, mmap() errors and process crashing is not.

Possibly? The convert_to_char() method which is defined in parse.c is using smart_str, php_var_serialize, estrndup, and smart_str_free which seems like it should all be PHP memory management, but I will freely admit that I have never really understood the internal memory management processes.
 [2020-05-05 10:20 UTC] cmb@php.net
> PHP OOM is a normal condition, mmap() errors and process
> crashing is not.

I don't think that there is any crash (segfault or such).  The
error message "mmap() failed: [12] Cannot allocate memory" comes
from zend_alloc.c[1], because the huge amount of memory couldn't
be allocated by the system, and consequently PHP errors with OOM.

It seems to me that everything behaves as expected, and this is
not a bug.

[1] <https://github.com/php/php-src/blob/php-7.2.30/Zend/zend_alloc.c#L431>
 [2020-05-06 04:06 UTC] bd808@php.net
The following pull request has been associated:

Patch Name: Remove support for non-scalar mapping keys
On GitHub:  https://github.com/php/pecl-file_formats-yaml/pull/47
Patch:      https://github.com/php/pecl-file_formats-yaml/pull/47.patch
 [2020-05-06 04:19 UTC] bd808@php.net
-Status: Assigned +Status: Closed
 [2020-05-06 04:19 UTC] bd808@php.net
I have merged a patch for this that will be part of the eventual v2.2.0 release. It is a breaking change in some sense, but upon reviewing the way that complex keys were being handled and looking at several other YAML implementations for languages where complex keys are not natively supported I decided that it was actually better to rip this "feature" out. The new behavior is to emit a warning when a complex key is encountered when parsing a YAML document, so its more of a soft break than a hard one.
 [2020-05-06 04:20 UTC] stas@php.net
-Type: Security +Type: Bug
 
PHP Copyright © 2001-2021 The PHP Group
All rights reserved.
Last updated: Mon Dec 06 03:03:34 2021 UTC