Skip to content

Commit 0543cd5

Browse files
committed
fix(lexer): Avoid recursive calls that may exhaust the call stack
1 parent ccdf743 commit 0543cd5

3 files changed

Lines changed: 60 additions & 36 deletions

File tree

‎src/parse/lexer.ts‎

Lines changed: 27 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -323,14 +323,14 @@ export class Lexer {
323323
return yield* this.parseBlockStart()
324324
}
325325

326-
private *parseBlockStart(): Generator<string, 'doc' | null> {
326+
private *parseBlockStart(): Generator<string, 'block-start' | 'doc' | null> {
327327
const [ch0, ch1] = this.peek(2)
328328
if (!ch1 && !this.atEnd) return this.setNext('block-start')
329329
if ((ch0 === '-' || ch0 === '?' || ch0 === ':') && isEmpty(ch1)) {
330330
const n = (yield* this.pushCount(1)) + (yield* this.pushSpaces(true))
331331
this.indentNext = this.indentValue + 1
332332
this.indentValue += n
333-
return yield* this.parseBlockStart()
333+
return 'block-start'
334334
}
335335
return 'doc'
336336
}
@@ -630,36 +630,34 @@ export class Lexer {
630630
}
631631

632632
private *pushIndicators(): Generator<string, number> {
633-
switch (this.charAt(0)) {
634-
case '!':
635-
return (
636-
(yield* this.pushTag()) +
637-
(yield* this.pushSpaces(true)) +
638-
(yield* this.pushIndicators())
639-
)
640-
case '&':
641-
return (
642-
(yield* this.pushUntil(isNotAnchorChar)) +
643-
(yield* this.pushSpaces(true)) +
644-
(yield* this.pushIndicators())
645-
)
646-
case '-': // this is an error
647-
case '?': // this is an error outside flow collections
648-
case ':': {
649-
const inFlow = this.flowLevel > 0
650-
const ch1 = this.charAt(1)
651-
if (isEmpty(ch1) || (inFlow && flowIndicatorChars.has(ch1))) {
652-
if (!inFlow) this.indentNext = this.indentValue + 1
653-
else if (this.flowKey) this.flowKey = false
654-
return (
655-
(yield* this.pushCount(1)) +
656-
(yield* this.pushSpaces(true)) +
657-
(yield* this.pushIndicators())
658-
)
633+
let n = 0
634+
loop: while (true) {
635+
switch (this.charAt(0)) {
636+
case '!':
637+
n += yield* this.pushTag()
638+
n += yield* this.pushSpaces(true)
639+
continue loop
640+
case '&':
641+
n += yield* this.pushUntil(isNotAnchorChar)
642+
n += yield* this.pushSpaces(true)
643+
continue loop
644+
case '-': // this is an error
645+
case '?': // this is an error outside flow collections
646+
case ':': {
647+
const inFlow = this.flowLevel > 0
648+
const ch1 = this.charAt(1)
649+
if (isEmpty(ch1) || (inFlow && flowIndicatorChars.has(ch1))) {
650+
if (!inFlow) this.indentNext = this.indentValue + 1
651+
else if (this.flowKey) this.flowKey = false
652+
n += yield* this.pushCount(1)
653+
n += yield* this.pushSpaces(true)
654+
continue loop
655+
}
659656
}
660657
}
658+
break loop
661659
}
662-
return 0
660+
return n
663661
}
664662

665663
private *pushTag() {

‎tests/doc/parse.ts‎

Lines changed: 21 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -454,13 +454,27 @@ describe('odd indentations', () => {
454454
})
455455

456456
describe('Resource exhaustion attacks', () => {
457-
test('Excessive recursion', () => {
458-
const depth = 5000
459-
const src = '['.repeat(depth) + '1' + ']'.repeat(depth)
460-
const doc = YAML.parseDocument(src)
461-
for (const error of doc.errors) {
462-
expect(error).toMatchObject({ code: 'RESOURCE_EXHAUSTION' })
463-
}
457+
describe('Excessive recursion', () => {
458+
test('Nested flow collections', () => {
459+
const depth = 5000
460+
const src = '['.repeat(depth) + '1' + ']'.repeat(depth)
461+
const doc = YAML.parseDocument(src)
462+
for (const error of doc.errors) {
463+
expect(error).toMatchObject({ code: 'RESOURCE_EXHAUSTION' })
464+
}
465+
})
466+
467+
test('excessive tag indicators', () => {
468+
const src = '! '.repeat(5000) + 'a'
469+
const doc = YAML.parseDocument(src)
470+
expect(doc.errors).toHaveLength(4999)
471+
})
472+
473+
test('excessive block sequence indicators', () => {
474+
const src = '- '.repeat(5000) + 'b'
475+
const doc = YAML.parseDocument(src)
476+
expect(doc.errors[0].code).toBe('RESOURCE_EXHAUSTION')
477+
})
464478
})
465479

466480
describe('Excessive entity expansion attacks', () => {

‎tests/lexer.ts‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,3 +36,15 @@ test('indented map + ... + unindented flow collection', () => {
3636
const res = Array.from(new Lexer().lex(src))
3737
expect(res).toEqual([DOC, ' ', ':', '\n', '...', '\n', DOC, '{', '\n', '}'])
3838
})
39+
40+
test('excessive tag indicators', () => {
41+
const src = '! '.repeat(5000) + 'a'
42+
const res = Array.from(new Lexer().lex(src))
43+
expect(res).toEqual([DOC, ...'! '.repeat(5000).split(''), SCALAR, 'a'])
44+
})
45+
46+
test('excessive block sequence indicators', () => {
47+
const src = '- '.repeat(5000) + 'b'
48+
const res = Array.from(new Lexer().lex(src))
49+
expect(res).toEqual([DOC, ...'- '.repeat(5000).split(''), SCALAR, 'b'])
50+
})

0 commit comments

Comments
 (0)