kc3-lang/libxml2

Diff

  • Show log

    Commit

  • Hash : 68eadabd
    Author : Nick Wellnhofer
    Date : 2020-07-11T21:32:10 

    Fix exponential runtime in xmlFARecurseDeterminism

In order to prevent visiting a state twice, states must be marked as
visited for the whole duration of graph traversal because states might
be reached by different paths. Otherwise state graphs like the
following can lead to exponential runtime:

  ->O-->O-->O-->O-->O->
     \ / \ / \ / \ /
      O   O   O   O

Reset the "visited" flag only after the graph was traversed.

xmlFAComputesDeterminism still has massive performance problems when
handling fuzzed input. By design, it has quadratic time complexity in
the number of reachable states. Some issues might also stem from
redundant epsilon transitions. With this fix, fuzzing regexes with a
maximum length of 100 becomes feasible at least.

Found with libFuzzer.

  • README

  •                   XML toolkit from the GNOME project

Full documentation is available on-line at
    http://xmlsoft.org/

This code is released under the MIT Licence see the Copyright file.

To build on an Unixised setup:
   ./configure ; make ; make install
   if the ./configure file does not exist, run ./autogen.sh instead.
To build on Windows:
   see instructions on win32/Readme.txt

To assert build quality:
   on an Unixised setup:
      run make tests
   otherwise:
       There is 3 standalone tools runtest.c runsuite.c testapi.c, which
       should compile as part of the build or as any application would.
       Launch them from this directory to get results, runtest checks 
       the proper functioning of libxml2 main APIs while testapi does
       a full coverage check. Report failures to the list.

To report bugs, follow the instructions at: 
  http://xmlsoft.org/bugs.html

A mailing-list xml@gnome.org is available, to subscribe:
    http://mail.gnome.org/mailman/listinfo/xml

The list archive is at:
    http://mail.gnome.org/archives/xml/

All technical answers asked privately will be automatically answered on
the list and archived for public access unless privacy is explicitly
required and justified.

Daniel Veillard

$Id$

kmx.io     mail     discord kmxgit v0.4.0