search

ElektraInitiative / libelektra

Elektra serves as a universal and secure framework to access configuration settings in a global, hierarchical key database.
https://www.libelektra.org
BSD 3-Clause "New" or "Revised" License
208 stars 123 forks source link

Circular links result in segmentation fault #4696

Closed 0x6178656c closed 10 months ago

0x6178656c commented 1 year ago

It appears that circular links (using overrides) lead to a stack overflow.

I implemented a fix for the most simple case in #4694 but after thinking some more about this I don't think that the solution is satisfactory.

In particular, circular link chains with more than one node would not be detected (see below for an example).

Since the actual problem seems to be a stack overflow, perhaps the most straightforward and robust solution would be to introduce a limit to the recursion depth. In this case probably the API of the functions would need to be changed to make this possible.

Is the idea with a maximum recursion depth reasonable? Are there other ways to abort the circular recursion?

Steps to Reproduce the Problem

kdb meta-set "spec:/circular" "override/#0" "/circular"
#> Create a new meta key for "spec:/circular" providing a link to "/circular" from "/circular"

kdb get "/circular"
# STDERR: Segmentation fault (core dumped)

Example with two hops:

kdb meta-set "spec:/circular1" "override/#0" "/circular2"
kdb meta-set "spec:/circular2" "override/#0" "/circular1"
kdb get "/circular1"
# SEGFAULT

Expected Result

kdb should not crash.

Actual Result

kdb crashes.

System Information

Further Log Files and Output

[root@c15ef13b0e5a workspace]# gdb --args kdb get "/circular"
GNU gdb (GDB) 12.1
Copyright (C) 2022 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-pc-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from kdb...
(gdb) run
Starting program: /workspace/elektra-install3/bin/kdb get /circular
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff79e58bf in ?? () from /usr/lib/libc.so.6
(gdb) backtrace
#0  0x00007ffff79e58bf in ?? () from /usr/lib/libc.so.6
#1  0x00007ffff7a07a9e in ?? () from /usr/lib/libc.so.6
#2  0x00007ffff79e1fa6 in snprintf () from /usr/lib/libc.so.6
#3  0x00007ffff7ec7eb6 in elektraWriteArrayNumber (newName=newName@entry=0x7fffff7ff829 "#", 
    newIndex=newIndex@entry=0) at /workspace/src/libs/elektra/keyset.c:1931
#4  0x00007ffff7ec8745 in elektraLookupBySpecLinks (ks=ks@entry=0x5555556e12b0, 
    specKey=specKey@entry=0x555556f349e0, buffer=buffer@entry=0x7fffff7ff820 "override/#")
    at /workspace/src/libs/elektra/keyset.c:1961
#5  0x00007ffff7ec8867 in elektraLookupBySpec (ks=ks@entry=0x5555556e12b0, 
    specKey=specKey@entry=0x555556f349e0, options=options@entry=524288)
    at /workspace/src/libs/elektra/keyset.c:2070
#6  0x00007ffff7ec8b46 in elektraLookupByCascading (ks=ks@entry=0x5555556e12b0, 
    key=key@entry=0x555556f347a0, options=options@entry=524288)
    at /workspace/src/libs/elektra/keyset.c:2124
#7  0x00007ffff7ec8411 in ksLookup (ks=ks@entry=0x5555556e12b0, key=key@entry=0x555556f347a0, 
    options=options@entry=524288) at /workspace/src/libs/elektra/keyset.c:2570
#8  0x00007ffff7ec872a in elektraLookupBySpecLinks (ks=ks@entry=0x5555556e12b0, 
    specKey=specKey@entry=0x555556f34550, buffer=buffer@entry=0x7fffff7ff9a0 "override/#0")
    at /workspace/src/libs/elektra/keyset.c:1973
#9  0x00007ffff7ec8867 in elektraLookupBySpec (ks=ks@entry=0x5555556e12b0, 
    specKey=specKey@entry=0x555556f34550, options=options@entry=524288)
    at /workspace/src/libs/elektra/keyset.c:2070
#10 0x00007ffff7ec8b46 in elektraLookupByCascading (ks=ks@entry=0x5555556e12b0, 
    key=key@entry=0x555556f34310, options=options@entry=524288)
    at /workspace/src/libs/elektra/keyset.c:2124
#11 0x00007ffff7ec8411 in ksLookup (ks=ks@entry=0x5555556e12b0, key=key@entry=0x555556f34310, 
    options=options@entry=524288) at /workspace/src/libs/elektra/keyset.c:2570
#12 0x00007ffff7ec872a in elektraLookupBySpecLinks (ks=ks@entry=0x5555556e12b0, 
    specKey=specKey@entry=0x555556f340c0, buffer=buffer@entry=0x7fffff7ffb20 "override/#0")
    at /workspace/src/libs/elektra/keyset.c:1973
#13 0x00007ffff7ec8867 in elektraLookupBySpec (ks=ks@entry=0x5555556e12b0, 
    specKey=specKey@entry=0x555556f340c0, options=options@entry=524288)
    at /workspace/src/libs/elektra/keyset.c:2070
#14 0x00007ffff7ec8b46 in elektraLookupByCascading (ks=ks@entry=0x5555556e12b0, 
    key=key@entry=0x555556f33e80, options=options@entry=524288)
    at /workspace/src/libs/elektra/keyset.c:2124
#15 0x00007ffff7ec8411 in ksLookup (ks=ks@entry=0x5555556e12b0, key=key@entry=0x555556f33e80, 
    options=options@entry=524288) at /workspace/src/libs/elektra/keyset.c:2570
#16 0x00007ffff7ec872a in elektraLookupBySpecLinks (ks=ks@entry=0x5555556e12b0, 
    specKey=specKey@entry=0x555556f33c30, buffer=buffer@entry=0x7fffff7ffca0 "override/#0")
    at /workspace/src/libs/elektra/keyset.c:1973
#17 0x00007ffff7ec8867 in elektraLookupBySpec (ks=ks@entry=0x5555556e12b0, 
    specKey=specKey@entry=0x555556f33c30, options=options@entry=524288)
    at /workspace/src/libs/elektra/keyset.c:2070
#18 0x00007ffff7ec8b46 in elektraLookupByCascading (ks=ks@entry=0x5555556e12b0, 
    key=key@entry=0x555556f339f0, options=options@entry=524288)
    at /workspace/src/libs/elektra/keyset.c:2124
#19 0x00007ffff7ec8411 in ksLookup (ks=ks@entry=0x5555556e12b0, key=key@entry=0x555556f339f0, 
    options=options@entry=524288) at /workspace/src/libs/elektra/keyset.c:2570
#20 0x00007ffff7ec872a in elektraLookupBySpecLinks (ks=ks@entry=0x5555556e12b0, 
    specKey=specKey@entry=0x555556f337a0, buffer=buffer@entry=0x7fffff7ffe20 "override/#0")
    at /workspace/src/libs/elektra/keyset.c:1973
kodebach commented 1 year ago

This is actually not just a problem with meta:/override, but all the metakeys that affect cascading lookup. You can also construct cycles with e.g. meta:/fallback or even meta:/namespace/#0 in there.

IMO we have 3 options:

  1. Leave it as is and just say "circular links are a problem"
  2. Add a reasonably high depth limit for cascading lookup (e.g. 255). Note: I wouldn't actually change the public ksLookup API for this. I'd just hardcode the limit and add a int depth argument to the internal functions.
  3. Actually checking for cycles requires keeping track of all visited nodes or building a graph structure and using something like Tarjan's SSC algorithm. Therefore it is not suitable for doing during ksLookup. However, we could add such a cycle check function to libelektra-ease: 
    // checks **all** keys in `ks` for potential cycles that would cause `ksLookup` stack overflow
bool elektraCheckLookupCycles (KeySet * ks);

    This function could then be called by the spec plugin. This would ensure that keysets returned by kdbGet are safe to use with ksLookup and would prevent you from successfully calling kdbSet on a keyset with cycles. If people modify the keyset or build their own and it might result in cycles, they can call the function directly too.

I would be in favour of option 3, since it is the most comprehensive solution.

0x6178656c commented 1 year ago

Thanks for the information.

I agree that 3 sounds the most promising.

Would it make sense to implement 2 and keep 3 as a to do? The goals of 2 and 3 are a bit different. 2 prevents Elektra from crashing due to a stack overflow and 3 aims at protecting a KDB instance from containing configuration containing reference loops.

github-actions[bot] commented 11 months ago

I mark this stale as it did not have any activity for one year. I'll close it in two weeks if no further activity occurs. If you want it to be alive again, ping by writing a message here or create a new issue with the remainder of this issue. Thank you for your contributions :sparkling_heart:

github-actions[bot] commented 10 months ago

I closed this now because it has been inactive for more than one year. If I closed it by mistake, please do not hesitate to reopen it or create a new issue with the remainder of this issue. Thank you for your contributions :sparkling_heart: