segfault in cgit

[Lukas Fleischer]

On Sun, Aug 21, 2011 at 07:46:05PM +0200, Lars Hjemli wrote:
> On Sun, Aug 21, 2011 at 18:00, Arun Persaud <apersaud at lbl.gov> wrote:
> > Hello
> >
> > I'm running cgit stable (9900ac022edfcfacee317d19a0f1d4d03b837b43) and
> > am getting segmentation faults (got them also with earlier versions).
> >
> > Unfortunately, I have no idea how to figure out what went wrong, but I
> > do have a core file in case that's interesting to anybody. Below is a
> > backtrace generated using gdb.
> >
> > Any idea what went wrong? Let me know if there is anything I should try
> > in case you need more output.
> >
> > HTH
> >
> > Arun
> >
> > [cgi-bin (master)]$ gdb cgit.cgi core
> > GNU gdb 6.8-debian
> > Copyright (C) 2008 Free Software Foundation, Inc.
> > License GPLv3+: GNU GPL version 3 or later
> > <http://gnu.org/licenses/gpl.html>
> > This is free software: you are free to change and redistribute it.
> > There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
> > and "show warranty" for details.
> > This GDB was configured as "x86_64-linux-gnu"...
> >
> > warning: Can't read pathname for load map: Input/output error.
> > Reading symbols from /usr/lib/libz.so.1...done.
> > Loaded symbols for /usr/lib/libz.so.1
> > Reading symbols from /lib/libpthread.so.0...done.
> > Loaded symbols for /lib/libpthread.so.0
> > Reading symbols from /usr/lib/libcrypto.so.0.9.8...done.
> > Loaded symbols for /usr/lib/libcrypto.so.0.9.8
> > Reading symbols from /lib/libc.so.6...done.
> > Loaded symbols for /lib/libc.so.6
> > Reading symbols from /lib/ld-linux-x86-64.so.2...done.
> > Loaded symbols for /lib64/ld-linux-x86-64.so.2
> > Reading symbols from /lib/libdl.so.2...done.
> > Loaded symbols for /lib/libdl.so.2
> > Core was generated by `cgit.cgi'.
> > Program terminated with signal 11, Segmentation fault.
> > [New process 16715]
> > #0  0x00000000004139c6 in longest_common_subsequence (
> >    A=0x731320
> > "if(a.Hg){a.LVM=a.VIEW;if(a.PLAIN_VIEW==a.VIEW){a.iV(true);}a.W.innerHTML='Press
> > any key or <a href=\"javascript:org_html_manager.showHelp();\">click
> > here</a> to proceed.<h2>Keyboard Shortcuts</h2><table"...,
> >    B=0x70ad70
> > "if(a.Hg){a.LVM=a.VIEW;if(a.PLAIN_VIEW==a.VIEW){a.iV(true);}a.W.innerHTML='Press
> > any key or <a href=\"javascript:org_html_manager.showHelp();\">click
> > here</a> to proceed.<h2>Keyboard Shortcuts</h2><table"...) at ui-ssdiff.c:38
> > 38                                      L[i][j] = (tmp1 > tmp2 ? tmp1 : tmp2);
> 
> I'd guess that the variable-length array L is becoming too big due to
> very long lines A and B in longest_common_subsequence():
>   http://hjemli.net/git/cgit/tree/ui-ssdiff.c?h=stable#n19
> 
> A simple fix might be to skip longest_common_subsequence if ((m +1) *
> (n + 1)) is greater than some constant value, e.g. 1024*1024.

Well, I just wanted to propose using calloc() instead. Having huge
arrays on the stack is a bad idea.

Anyway, there should be some limitation here. LCS takes O(n * m) time
and needs O(n * m) space, so we might be prone to DoS here (even though
this is only exploitable by some user with push access to the
repositories). Your proposal is a step in the right direction.