[YAMLIO] Support non-null-terminated inputs

[scott.linder]

Summary

In some places the parser guards against dereferencing End, while in
others it relies on the presence of a trailing '\0' to elide checks.

Add the remaining guards needed to ensure the parser never attempts to
dereference End, making it safe to not require a null-terminated input
buffer.

Update fuzzer harness so that it doesn't ensure null-terminated inputs.

Some of the regression tests were written by inspection, and some are
cases caught by the fuzzer which required additional fixes in the
parser.

[arsenm]

ping

[arsenm]

ping

[bkramer]

The parser used to rely on the \0 being present. Was that fixed?

[arsenm]

In D84050#2189370, @bkramer wrote:

The parser used to rely on the \0 being present. Was that fixed?

Do you know where this assumption was? I couldn't find it, but also couldn't find any commits that seemed to "fix" it. I haven't seen a sanitizer error yet

[dexonsmith]

In D84050#2242755, @arsenm wrote:

In D84050#2189370, @bkramer wrote:

The parser used to rely on the \0 being present. Was that fixed?

Do you know where this assumption was? I couldn't find it, but also couldn't find any commits that seemed to "fix" it. I haven't seen a sanitizer error yet

I just did a quick scan and I can't find any such assumption either. @Bigcheese, do remember what the original intent was?

llvm/lib/Support/YAMLParser.cpp

773

Please spell this /*RequiresNullTerminator=*/false.

[grimar]

This should have a unittest probably, if fixes something.

[scott.linder]

Try to keep the parser from running off the end of the buffer and dereferencing
the result; add some unit tests to try to stress pieces being changed.

[scott.linder]

I tried to address the issues brought up, but I'm not particularly confident I found every case in the parser where it assumes End is OK to dereference. I think the presence of a null-terminator just made these bugs harder to detect, but as far as I can tell they are in fact bugs (i.e. End is documented as being one-past-the-end, and a lot of other places do guard against Current == End).

I didn't do a stellar job with unit testing either, I essentially just tried to produce at least enough test cases to stress the changes I made. I considered updating all of the existing tests to not use null-terminated buffers, or to check with both, but wanted to see what people thought first.

As a note, the tests will only deterministically fail with ASan enabled, but I don't know a reliable way to avoid that.

[scott.linder]

Ignore this diff, I thought I had run check-all but evidently I hadn't. I'll look at what I broke in the spec tests and post a revised patch.

[dexonsmith]

In D84050#2389985, @scott.linder wrote:

As a note, the tests will only deterministically fail with ASan enabled, but I don't know a reliable way to avoid that.

That's fine, we'll always have ASan bots to catch these. Not ideal, but reasonable for this kind of situation.

[Bigcheese]

In D84050#2315437, @dexonsmith wrote:

In D84050#2242755, @arsenm wrote:

In D84050#2189370, @bkramer wrote:

The parser used to rely on the \0 being present. Was that fixed?

Do you know where this assumption was? I couldn't find it, but also couldn't find any commits that seemed to "fix" it. I haven't seen a sanitizer error yet

I just did a quick scan and I can't find any such assumption either. @Bigcheese, do remember what the original intent was?

All I recall at this point is that I required a null terminator for the same reason Clang does, to remove the constant need to check for Current != End. This probably makes a lot more sense for Clang to do as it's rare to compile source code not in a file, which may not always be true for the YAML parser. I'm fine with removing that assumption.

[scott.linder]

Restore the correct behavior of Scanner::scanAliasOrAnchor, last version of the patch mistakenly changed Token.Range when only intending to fix the error checking around an empty alias/anchor.

I think this version now removes the assumption that End points to a dereferencable '\0', but I'm not sure how to go about testing this comprehensively.

[dexonsmith]

In D84050#2391741, @scott.linder wrote:

Restore the correct behavior of Scanner::scanAliasOrAnchor, last version of the patch mistakenly changed Token.Range when only intending to fix the error checking around an empty alias/anchor.

I think this version now removes the assumption that End points to a dereferencable '\0', but I'm not sure how to go about testing this comprehensively.

One idea would be to hack the parser to always duplicate the input, append a bad character (like '\1'), and parse the new buffer with the original bounds. If something reads too far it would likely get upset at the bad character. Running the test suites for LLVM and Clang with that hack might be enough coverage.

Is there a libfuzzer instance for the yaml parser? That's probably the ideal thing to do, and if it's already set up maybe it's not too hard.

[dexonsmith]

llvm/lib/Support/YAMLParser.cpp

1409–1410

I don't have an opinion on the best order of these two lines, but if you want to flip them please do so in a separate NFC commit (and revert the change from this patch to make it as clean as possible).

1411

Please run git-clang-format or similar to fix the spacing on the lines touched.

1424

This looks like a fix for a logic bug, not directly related to null-termination; can it be committed separately ahead of time? Please also add a test that covers it.

[scott.linder]

Address feedback

• Correct a spurious reordering of some lines
• Format touched lines
• Split off semantically distinct patch for anchor/alias diagnostic bug

[scott.linder]

llvm/lib/Support/YAMLParser.cpp

1409–1410

My mistake, I didn't look over the diff closely enough before posting. Fixed!

[scott.linder]

I ran the fuzzer and quickly found two places I had missed. I've been running the fuzzer for about a half hour now and haven't seen another crash, so I am tentatively posting the patch. I'll leave the fuzzer running for as long as I reasonably can to try to find additional cases.

[scott.linder]

In D84050#2392467, @dexonsmith wrote:

In D84050#2391741, @scott.linder wrote:

Restore the correct behavior of Scanner::scanAliasOrAnchor, last version of the patch mistakenly changed Token.Range when only intending to fix the error checking around an empty alias/anchor.

I think this version now removes the assumption that End points to a dereferencable '\0', but I'm not sure how to go about testing this comprehensively.

One idea would be to hack the parser to always duplicate the input, append a bad character (like '\1'), and parse the new buffer with the original bounds. If something reads too far it would likely get upset at the bad character. Running the test suites for LLVM and Clang with that hack might be enough coverage.

Is there a libfuzzer instance for the yaml parser? That's probably the ideal thing to do, and if it's already set up maybe it's not too hard.

Also thank you for mentioning libFuzzer! It was really painless and feels like the best thing short of a proof to validate the change.

[dexonsmith]

llvm/tools/llvm-yaml-parser-fuzzer/yaml-parser-fuzzer.cpp

33–50

I wonder if it would also be useful to have logic like this:

auto testYaml = [](const uint8_t *Data, size_t Size) {
  // return true if it parses.
};

// Test that there's no crash when parsing the raw data.
testYaml(Data, Size);

// Test with 0s filtered out.
std::string Input(reinterpret_cast<const char *>(Data), Size);
Input.erase(std::remove(Input.begin(), Input.end(), 0), Input.end());
Size = Input.size();
bool TerminatedBy0 = testYaml(Input.data(), Size);

// Test that an invalid character after the input has no effect.
Input.push_back(1);
if (testYaml(Input.data(), Size) != TerminatedBy0)
  __builtin_trap(...);
return 0;

[scott.linder]

I added something along the lines of what you proposed, let me know what you
think. I also switched to a vector<uint8_t> to get more explicit control over
the terminator, and to yaml::Stream to be able to directly call validate()
such that every document is checked (in case the fuzzer produces inputs with
multiple documents).

I had also considered trying to duplicate the existing parser to do comparitive
testing, but I wasn't sure the best way to go about it. I could just build the
compiler twice, and then have an instance of the fuzzer feed into both and
compare their results. Let me know if you would find this helpful, and I can
do the test and just not commit the result.

[scott.linder]

I also added calls to vector::shrink_to_fit to maybe make it slightly more likely for a sanitizer without c++ STL annotations to catch out-of-bounds accesses, but if this is just noise I'm happy to remove them.

[scott.linder]

Remove one redundant call to vector::shrink_to_fit

[dexonsmith]

This LGTM now, thanks for integrating this into the fuzzer! I have a couple of other suggestions, but it's up to you whether to apply them.

llvm/tools/llvm-yaml-parser-fuzzer/yaml-parser-fuzzer.cpp

11

It may be nice to have a using namespace llvm; here and remove the llvm::s below. Up to you.

12

This could probably be isValidYaml to silence the clang-tidy warning. LLVM_FuzzerTestOneInput has to be how it us, but we could still modify this.

llvm/lib/Support/YAMLParser.cpp

 ///        A length of 0 represents an error.
 using UTF8Decoded = std::pair<uint32_t, unsigned>;
 
 static UTF8Decoded decodeUTF8(StringRef Range) {
   StringRef::iterator Position= Range.begin();
   StringRef::iterator End = Range.end();
   // 1 byte: [0x00, 0x7f]
   // Bit pattern: 0xxxxxxx
-  if ((*Position & 0x80) == 0) {
-     return std::make_pair(*Position, 1);
+  if (Position < End && (*Position & 0x80) == 0) {
   }
   // 2 bytes: [0x80, 0x7ff]
   // Bit pattern: 110xxxxx 10xxxxxx
-  if (Position + 1 != End &&
-      ((*Position & 0xE0) == 0xC0) &&
+  if (Position + 1 < End && ((*Position & 0xE0) == 0xC0) &&
       ((*(Position + 1) & 0xC0) == 0x80)) {
     uint32_t codepoint = ((*Position & 0x1F) << 6) |
                           (*(Position + 1) & 0x3F);
     if (codepoint >= 0x80)
       return std::make_pair(codepoint, 2);
   }
   // 3 bytes: [0x8000, 0xffff]
   // Bit pattern: 1110xxxx 10xxxxxx 10xxxxxx
-  if (Position + 2 != End &&
-      ((*Position & 0xF0) == 0xE0) &&
+  if (Position + 2 < End && ((*Position & 0xF0) == 0xE0) &&
       ((*(Position + 1) & 0xC0) == 0x80) &&
       ((*(Position + 2) & 0xC0) == 0x80)) {
     uint32_t codepoint = ((*Position & 0x0F) << 12) |
                          ((*(Position + 1) & 0x3F) << 6) |
                           (*(Position + 2) & 0x3F);
     // Codepoints between 0xD800 and 0xDFFF are invalid, as
     // they are high / low surrogate halves used by UTF-16.
     if (codepoint >= 0x800 &&
         (codepoint < 0xD800 || codepoint > 0xDFFF))
       return std::make_pair(codepoint, 3);
   }
   // 4 bytes: [0x10000, 0x10FFFF]
   // Bit pattern: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
-  if (Position + 3 != End &&
-      ((*Position & 0xF8) == 0xF0) &&
+  if (Position + 3 < End && ((*Position & 0xF8) == 0xF0) &&
       ((*(Position + 1) & 0xC0) == 0x80) &&
       ((*(Position + 2) & 0xC0) == 0x80) &&
       ((*(Position + 3) & 0xC0) == 0x80)) {
     uint32_t codepoint = ((*Position & 0x07) << 18) |
                          ((*(Position + 1) & 0x3F) << 12) |
                          ((*(Position + 2) & 0x3F) << 6) |
                           (*(Position + 3) & 0x3F);
     if (codepoint >= 0x10000 && codepoint <= 0x10FFFF)
void Scanner::init(MemoryBufferRef Buffer) {
   Indent = -1;
   Column = 0;
   Line = 0;
   FlowLevel = 0;
   IsStartOfStream = true;
   IsSimpleKeyAllowed = true;
   Failed = false;
   std::unique_ptr<MemoryBuffer> InputBufferOwner =
-      MemoryBuffer::getMemBuffer(Buffer);
+      MemoryBuffer::getMemBuffer(Buffer, /*RequiresNullTerminator=*/false);
   SM.AddNewSourceBuffer(std::move(InputBufferOwner), SMLoc());
 }
 
 Token &Scanner::peekNext() {
   // If the current token is a possible simple key, keep parsing until we
   // can confirm.
   bool NeedMore = false;
   while (true) {
if (Indent < ToColumn) {
     T.Kind = Kind;
     T.Range = StringRef(Current, 0);
     TokenQueue.insert(InsertPoint, T);
   }
   return true;
 }
 
 void Scanner::skipComment() {
-  if (*Current != '#')
+  if (Current == End || *Current != '#')
     return;
   while (true) {
     // This may skip more than one byte, thus Column is only incremented
     // for code points.
     StringRef::iterator I = skip_nb_char(Current);
     if (I == Current)
       break;
     Current = I;
     ++Column;
   }
 }
 
 void Scanner::scanToNextToken() {
   while (true) {
-    while (*Current == ' ' || *Current == '\t') {
+    while (Current != End && (*Current == ' ' || *Current == '\t')) {
       skip(1);
     }
 
     skipComment();
 
     // Skip EOL.
     StringRef::iterator i = skip_b_break(Current);
     if (i == Current)
do {
         ++Current;
       // Repeat until the previous character was not a '\' or was an escaped
       // backslash.
     } while (   Current != End
              && *(Current - 1) == '\\'
              && wasEscaped(Start + 1, Current));
   } else {
     skip(1);
-    while (true) {
+    while (Current != End) {
       // Skip a ' followed by another '.
       if (Current + 1 < End && *Current == '\'' && *(Current + 1) == '\'') {
         skip(2);
         continue;
       } else if (*Current == '\'')
         break;
       StringRef::iterator i = skip_nb_char(Current);
       if (i == Current) {

 }
 
 bool Scanner::scanPlainScalar() {
   StringRef::iterator Start = Current;
   unsigned ColStart = Column;
   unsigned LeadingBlanks = 0;
   assert(Indent >= -1 && "Indent must be >= -1 !");
   unsigned indent = static_cast<unsigned>(Indent + 1);
-  while (true) {
+  while (Current != End) {
     if (*Current == '#')
       break;
 
-    while (!isBlankOrBreak(Current)) {
-      if (  FlowLevel && *Current == ':'
-          && !(isBlankOrBreak(Current + 1) || *(Current + 1) == ',')) {
+    while (Current != End && !isBlankOrBreak(Current)) {
+      if (FlowLevel && *Current == ':' &&
+          (Current + 1 == End ||
+           !(isBlankOrBreak(Current + 1) || *(Current + 1) == ','))) {
         setError("Found unexpected ':' while scanning a plain scalar", Current);
         return false;
       }
 
       // Check for the end of the plain scalar.
       if (  (*Current == ':' && isBlankOrBreak(Current + 1))
           || (  FlowLevel
           && (StringRef(Current, 1).find_first_of(",:?[]{}")
bool Scanner::scanPlainScalar() {
 
   IsSimpleKeyAllowed = false;
 
   return true;
 }
 
 bool Scanner::scanAliasOrAnchor(bool IsAlias) {
   StringRef::iterator Start = Current;
   unsigned ColStart = Column;
   skip(1);
-  while(true) {
+  while (Current != End) {
     if (   *Current == '[' || *Current == ']'
         || *Current == '{' || *Current == '}'
         || *Current == ','
         || *Current == ':')
       break;
     StringRef::iterator i = skip_ns_char(Current);
     if (i == Current)
       break;
     Current = i;
     ++Column;
   }
 
   if (Start + 1 == Current) {
     setError("Got empty alias or anchor", Start);
     return false;
   }
 
   Token T;
   T.Kind = IsAlias ? Token::TK_Alias : Token::TK_Anchor;
   T.Range = StringRef(Start, Current - Start);
   TokenQueue.push_back(T);

llvm/tools/llvm-yaml-parser-fuzzer/yaml-parser-fuzzer.cpp

 //===-- yaml-parser-fuzzer.cpp - Fuzzer for YAML parser -------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/YAMLParser.h"
 
 using namespace llvm;
 
 static bool isValidYaml(const uint8_t *Data, size_t Size) {
   SourceMgr SM;
   yaml::Stream Stream(StringRef(reinterpret_cast<const char *>(Data), Size),
                       SM);
   return Stream.validate();
 }
 
 extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
   std::vector<uint8_t> Input(Data, Data + Size);
 
+  // Ensure we don't crash on any arbitrary byte string.
+  isValidYaml(Input.data(), Input.size());
+
+  // Ensure we don't crash on byte strings with no null characters.
+  Input.erase(std::remove(Input.begin(), Input.end(), 0), Input.end());
+  Input.shrink_to_fit();
+  bool IsValidWithout0s = isValidYaml(Input.data(), Input.size());
+
   // Ensure we don't crash on byte strings where the only null character is
   // one-past-the-end of the actual input to the parser.
-  Input.erase(std::remove(Input.begin(), Input.end(), 0), Input.end());
   Input.push_back(0);
   Input.shrink_to_fit();
-  isValidYaml(Input.data(), Input.size() - 1);
+  bool IsValidWhen0Terminated = isValidYaml(Input.data(), Input.size() - 1);
+
+  // Ensure we don't crash on byte strings with no null characters, but with
+  // an invalid character one-past-the-end of the actual input to the parser.
+  Input.back() = 1;
+  bool IsValidWhen1Terminated = isValidYaml(Input.data(), Input.size() - 1);
+
+  // The parser should either accept all of these inputs, or reject all of
+  // them, because the parser sees an identical byte string in each case. This
+  // should hopefully catch some cases where the parser is sensitive to what is
+  // present one-past-the-end of the actual input.
+  if (IsValidWithout0s != IsValidWhen0Terminated ||
+      IsValidWhen0Terminated != IsValidWhen1Terminated)
+    LLVM_BUILTIN_TRAP;
 
   return 0;
 }

llvm/unittests/Support/YAMLIOTest.cpp

TEST(YAMLIO, TestEmptyAlias) {
   Input yin("&");
   EXPECT_FALSE(yin.setCurrentDocument());
   EXPECT_TRUE(yin.error());
 }
 
 TEST(YAMLIO, TestEmptyAnchor) {
   Input yin("*");
   EXPECT_FALSE(yin.setCurrentDocument());
+}
+
+TEST(YAMLIO, TestScannerNoNullEmpty) {
+  std::vector<char> str{};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
+  EXPECT_FALSE(yin.error());
+}
+
+TEST(YAMLIO, TestScannerNoNullSequenceOfNull) {
+  std::vector<char> str{'-'};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
+  EXPECT_FALSE(yin.error());
+}
+
+TEST(YAMLIO, TestScannerNoNullSimpleSequence) {
+  std::vector<char> str{'-', ' ', 'a'};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
+  EXPECT_FALSE(yin.error());
+}
+
+TEST(YAMLIO, TestScannerNoNullUnbalancedMap) {
+  std::vector<char> str{'{'};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
+  EXPECT_TRUE(yin.error());
+}
+
+TEST(YAMLIO, TestScannerNoNullEmptyMap) {
+  std::vector<char> str{'{', '}'};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
+  EXPECT_FALSE(yin.error());
+}
+
+TEST(YAMLIO, TestScannerNoNullUnbalancedSequence) {
+  std::vector<char> str{'['};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
+  EXPECT_TRUE(yin.error());
+}
+
+TEST(YAMLIO, TestScannerNoNullEmptySequence) {
+  std::vector<char> str{'[', ']'};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
+  EXPECT_FALSE(yin.error());
+}
+
+TEST(YAMLIO, TestScannerNoNullScalarUnbalancedDoubleQuote) {
+  std::vector<char> str{'"'};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
+  EXPECT_TRUE(yin.error());
+}
+
+TEST(YAMLIO, TestScannerNoNullScalarUnbalancedSingleQuote) {
+  std::vector<char> str{'\''};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
+  EXPECT_TRUE(yin.error());
+}
+
+TEST(YAMLIO, TestScannerNoNullEmptyAlias) {
+  std::vector<char> str{'&'};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
+  EXPECT_TRUE(yin.error());
+}
+
+TEST(YAMLIO, TestScannerNoNullEmptyAnchor) {
+  std::vector<char> str{'*'};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
+  EXPECT_TRUE(yin.error());
+}
+
+TEST(YAMLIO, TestScannerNoNullDecodeInvalidUTF8) {
+  std::vector<char> str{'\xef'};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
+  EXPECT_TRUE(yin.error());
+}
+
+TEST(YAMLIO, TestScannerNoNullScanPlainScalarInFlow) {
+  std::vector<char> str{'{', 'a', ':'};
+  Input yin(llvm::StringRef(str.data(), str.size()));
+  yin.setCurrentDocument();
   EXPECT_TRUE(yin.error());
 }