Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

OSS-Fuzz/ClusterFuzz finding 66812 #839

Closed
hartwork opened this issue Mar 3, 2024 · 8 comments
Closed

OSS-Fuzz/ClusterFuzz finding 66812 #839

hartwork opened this issue Mar 3, 2024 · 8 comments

Comments

@hartwork
Copy link
Member

hartwork commented Mar 3, 2024

Issue

This is the public side of soon-public (access protected) oss-fuzz Expat finding:
Issue 66812: expat:xml_parse_fuzzer_UTF-16: Timeout in xml_parse_fuzzer_UTF-16.

The three key (access protected) contained links are:

The reproducer (original attached as file clusterfuzz-testcase-minimized-xml_parse_fuzzer_UTF-16-5187173185814528-timeout-original.xml.txt) is essentially this two-file case:

File one.xml:

<!DOCTYPE doc SYSTEM "two.dtd">
<doc>&g1;</doc>

File two.dtd:

<!ENTITY % p1 '%p1'>
<!ENTITY g1 '%p1;'>

The original's SHA245 sum is 6b870c78cff9efe41f1060277f434da98b9f78e9159baf4cb95f034e890ac087.

The regression link effectively links to be47f6d...716fd10 (which makes good sense since these changes increase fuzzing coverage).

Analysis

ClusterFuzz uncovered two things at once here:

  • Direct recursion (a -> a in contrast to indirect recursion a -> b -> a) of parameter entities (reference syntax %name;) was previously not detected in the external subset — file two.dtd in the example above) — but it is forbidden by the XML spec and was also causing undefined behavior at runtime.
    # ./fuzz/xml_parse_fuzzer_UTF-8 [..]/clusterfuzz-testcase-minimized-xml_parse_fuzzer_UTF-16-5187173185814528-timeout-original.xml.txt
    INFO: Running with entropic power schedule (0xFF, 100).
    INFO: Seed: 3441536382
    INFO: Loaded 1 modules   (21351 inline 8-bit counters): 21351 [0x558df02c6000, 0x558df02cb367), 
    INFO: Loaded 1 PC tables (21351 PCs): 21351 [0x558df02cb368,0x558df031e9d8), 
    ./fuzz/xml_parse_fuzzer_UTF-8: Running 1 inputs 1 time(s) each.
    Running: [..]/clusterfuzz-testcase-minimized-xml_parse_fuzzer_UTF-16-5187173185814528-timeout-original.xml.txt
    [..]/expat/lib/xmlparse.c:6273:46: runtime error: applying zero offset to null pointer
    SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior [..]/expat/lib/xmlparse.c:6273:46 in 
    Pull request Reject direct parameter entity recursion (part of #839) #841 addresses that problem.
  • The way that the fuzzing code uses external parsers (created via function XML_ExternalEntityParserCreate) caused a timeout revealing that due to the lack of any direct input bytes from the parent parser, the amplification ratio calculated by accountingGetCurrentAmplification was constantly reported as 1.0 and hence had little chance of stopping billion laughs attacks in practice. Pull request [CVE-2024-28757] Prevent billion laughs attacks in isolated external parser (part of #839) #842 addresses that problem.

Two related side notes:

  • ClusterFuzz leaked part of this finding — the recursion aspect — to the public corpus a few days ago as case f9b6ba558667913f4554395e039c01f6d8217b43 that later disappeared from the public corpus again.

  • Statement…

    If the same entity is declared more than once, the first declaration encountered is binding;

    …in section 4.2 Entity Declarations of the XML spec is worth noting, emphasis mine.

CC @catenacyber @RMJ10 @Snild-Sony

@Snild-Sony
Copy link
Contributor

ClusterFuzz leaked part of this finding — the recursion aspect — to the public corpus a few days ago as case f9b6ba558667913f4554395e039c01f6d8217b43 that later disappeared from the public corpus again.

...which made for a very confusing "regression" in CI runs for an innocent PR. :)

@hartwork
Copy link
Member Author

hartwork commented Mar 6, 2024

ClusterFuzz leaked part of this finding — the recursion aspect — to the public corpus a few days ago as case f9b6ba558667913f4554395e039c01f6d8217b43 that later disappeared from the public corpus again.

...which made for a very confusing "regression" in CI runs for an innocent PR. :)

Indeed. I had to disable the fuzzing regression testing workflow temporarily because of that. Would be great to understand if that leak was human- or machine-made.

hartwork added a commit that referenced this issue Mar 6, 2024
…arser

When parsing DTD content with code like ..

  XML_Parser parser = XML_ParserCreate(NULL);
  XML_Parser ext_parser = XML_ExternalEntityParserCreate(parser, NULL, NULL);
  enum XML_Status status = XML_Parse(ext_parser, doc, (int)strlen(doc), XML_TRUE);

.. there are 0 bytes accounted as direct input and all input from `doc` accounted
as indirect input.  Now function accountingGetCurrentAmplification cannot calculate
the current amplification ratio as "(direct + indirect) / direct", and it did refuse
to divide by 0 as one would expect, but it returned 1.0 for this case to indicate
no amplification over direct input.  As a result, billion laughs attacks from
DTD-only input were not detected with this isolated way of using an external parser.

The new appraoch is to assume direct input of length not 0 but 22 -- derived from
ghost input "<!ENTITY a SYSTEM 'b'>", the shortest possible way to include an external
DTD --, and do the usual "(direct + indirect) / direct" math with "direct := 22".

GitHub issue #839 has more details on this issue and its origin in ClusterFuzz
finding 66812.
hartwork added a commit that referenced this issue Mar 6, 2024
…arser

When parsing DTD content with code like ..

  XML_Parser parser = XML_ParserCreate(NULL);
  XML_Parser ext_parser = XML_ExternalEntityParserCreate(parser, NULL, NULL);
  enum XML_Status status = XML_Parse(ext_parser, doc, (int)strlen(doc), XML_TRUE);

.. there are 0 bytes accounted as direct input and all input from `doc` accounted
as indirect input.  Now function accountingGetCurrentAmplification cannot calculate
the current amplification ratio as "(direct + indirect) / direct", and it did refuse
to divide by 0 as one would expect, but it returned 1.0 for this case to indicate
no amplification over direct input.  As a result, billion laughs attacks from
DTD-only input were not detected with this isolated way of using an external parser.

The new approach is to assume direct input of length not 0 but 22 -- derived from
ghost input "<!ENTITY a SYSTEM 'b'>", the shortest possible way to include an external
DTD --, and do the usual "(direct + indirect) / direct" math with "direct := 22".

GitHub issue #839 has more details on this issue and its origin in ClusterFuzz
finding 66812.
@catenacyber
Copy link
Contributor

Thanks for the great report

Would be great to understand if that leak was human- or machine-made.

I do not think any human intervened.

hartwork added a commit that referenced this issue Mar 7, 2024
…er-entity-recursion

Reject direct parameter entity recursion (part of #839)
@hartwork
Copy link
Member Author

hartwork commented Mar 7, 2024

I had to disable the fuzzing regression testing workflow temporarily because of that.

FYI I re-enabled that workflow after merge of #841 now.

hartwork added a commit that referenced this issue Mar 7, 2024
…ed-external-parser

Prevent billion laughs attacks in isolated external parser (part of #839)
@hartwork hartwork closed this as completed Mar 7, 2024
@hartwork hartwork changed the title ClusterFuzz finding 66812 OSS-Fuzz/ClusterFuzz finding 66812 Mar 10, 2024
@PshySimon
Copy link

PshySimon commented Mar 21, 2024

Sorry to bother you, I'm a bit confused about these two test cases.
{"<!ENTITY % p1 '%p1;'>"
"<!ENTITY % p1 'first declaration wins'>",
XML_STATUS_ERROR},
{"<!ENTITY % p1 'first declaration wins'>"
"<!ENTITY % p1 '%p1;'>",
XML_STATUS_OK}

I can't see any difference between these two cases, why do they have different results?

@Snild-Sony
Copy link
Contributor

I believe this is what @hartwork was explaining with this quote above:

  • Statement…

    If the same entity is declared more than once, the first declaration encountered is binding;

    …in section 4.2 Entity Declarations of the XML spec is worth noting, emphasis mine.

The full sentence makes it a little clearer:

If the same entity is declared more than once, the first declaration encountered is binding;at user option, an XML processor may issue a warning if entities are declared multiple times.

So, the test added in #841 says:

  • <!ENTITY % p1 '%p1;'> is bad.
  • <!ENTITY % p1 '%p1;'><!ENTITY % p1 'first declaration wins'> is bad, because the recursive declaration comes first.
  • <!ENTITY % p1 'first declaration wins'><!ENTITY % p1 '%p1;'> is fine, because the first declaration is OK and the second one can be (and, I'm guessing, is) ignored.

@PshySimon
Copy link

Oh, I understand now. Thank you for your explanation.

@hartwork
Copy link
Member Author

@Snild-Sony well said, thank you!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

4 participants