search

hercules-team / augeas

A configuration editing tool and API
http://augeas.net/
GNU Lesser General Public License v2.1
478 stars 198 forks source link

oss-fuzz: timeout，The "determinize" function in src/fa.c exists a infinite loop, that always alloc the memory... #709

Open MR-sanman opened 3 years ago

MR-sanman commented 3 years ago

Hi Team,

I get an error in ageaus-1.12.0 when doing oss_fuzz test(here master is same as 1.12.0), the details are as follows:

ALARM: working on the last Unit for 25 seconds
       and the timeout value is 25 (use -timeout=N to change)
==8== ERROR: libFuzzer: timeout after 25 seconds
    #0 0x52a281 in __sanitizer_print_stack_trace /src/llvm/projects/compiler-rt/lib/asan/asan_stack.cpp:86:3
    #1 0x474218 in fuzzer::PrintStackTrace() /src/llvm/projects/compiler-rt/lib/fuzzer/FuzzerUtil.cpp:205:5
    #2 0x458709 in fuzzer::Fuzzer::AlarmCallback() /src/llvm/projects/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:300:5
    #3 0x7fe6c081f38f  (/lib/x86_64-linux-gnu/libpthread.so.0+0x1138f)
    #4 0x541bf9 in add /src/llvm/projects/compiler-rt/lib/sanitizer_common/sanitizer_hash.h:27:7
    #5 0x541bf9 in hash /src/llvm/projects/compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp:54:44
    #6 0x541bf9 in __sanitizer::StackDepotBase<__sanitizer::StackDepotNode, 1, 20>::Put(__sanitizer::StackTrace, bool*) /src/llvm/projects/compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h:101:12
    #7 0x541b26 in __sanitizer::StackDepotPut(__sanitizer::StackTrace) /src/llvm/projects/compiler-rt/lib/sanitizer_common/sanitizer_stackdepot.cpp:98:33
    #8 0x4aee52 in __asan::Allocator::QuarantineChunk(__asan::AsanChunk*, void*, __sanitizer::BufferedStackTrace*) /src/llvm/projects/compiler-rt/lib/asan/asan_allocator.cpp:573:26
    #9 0x4ab42b in __asan::Allocator::Reallocate(void*, unsigned long, __sanitizer::BufferedStackTrace*) /src/llvm/projects/compiler-rt/lib/asan/asan_allocator.cpp:670:7
    #10 0x4ab2c5 in __asan::asan_realloc(void*, unsigned long, __sanitizer::BufferedStackTrace*) /src/llvm/projects/compiler-rt/lib/asan/asan_allocator.cpp:904:34
    #11 0x521a3a in realloc /src/llvm/projects/compiler-rt/lib/asan/asan_malloc_linux.cpp:165:10
    #12 0x578038 in mem_realloc_n /src/augeas/src/memory.c:98:11
    #13 0x56e700 in state_set_expand /src/augeas/src/fa.c:553:9
    #14 0x56ef78 in state_set_add /src/augeas/src/fa.c:664:17
    #15 0x55e417 in determinize /src/augeas/src/fa.c:1343:25
    #16 0x55ee49 in fa_complement /src/augeas/src/fa.c:2438:5
    #17 0x55f385 in fa_minus /src/augeas/src/fa.c:2459:23
    #18 0x553c00 in LLVMFuzzerTestOneInput /src/augeas/augeas_fa_fuzzer.cc:60:11
    #19 0x459e91 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) /src/llvm/projects/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:556:15
    #20 0x444ab1 in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) /src/llvm/projects/compiler-rt/lib/fuzzer/FuzzerDriver.cpp:292:6
    #21 0x44a76e in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) /src/llvm/projects/compiler-rt/lib/fuzzer/FuzzerDriver.cpp:774:9
    #22 0x4748e2 in main /src/llvm/projects/compiler-rt/lib/fuzzer/FuzzerMain.cpp:19:10
    #23 0x7fe6bfe4282f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
    #24 0x41de68 in _start (/out/augeas_fa_fuzzer+0x41de68)

SUMMARY: libFuzzer: timeout

I use gdb to debug that detail as follows

root@63b6623d2fb5:/out/augeas/augeas_sp1/src# gdb --args ../../augeas_fa_fuzzer_sp1 ../../timeout-4c53e93160ee701bf55181ea328dff24cf030380
GNU gdb (Ubuntu 7.11.1-0ubuntu1~16.5) 7.11.1
Copyright (C) 2016 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".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://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 ../../augeas_fa_fuzzer_sp1...done.
(gdb) r
Starting program: /out/augeas/augeas_fa_fuzzer_sp1 ../../timeout-4c53e93160ee701bf55181ea328dff24cf030380
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
INFO: Seed: 3712520980
INFO: Loaded 1 modules   (1964 inline 8-bit counters): 1964 [0x7e1c40, 0x7e23ec),
INFO: Loaded 1 PC tables (1964 PCs): 1964 [0x595e48,0x59d908),
[New Thread 0x7ffff2679700 (LWP 85)]
/out/augeas/augeas_fa_fuzzer_sp1: Running 1 inputs 1 time(s) each.
Running: ../../timeout-4c53e93160ee701bf55181ea328dff24cf030380
==81== ERROR: libFuzzer: out-of-memory (used: 2050Mb; limit: 2048Mb)
   To change the out-of-memory limit use -rss_limit_mb=<N>

SUMMARY: libFuzzer: out-of-memory
[Thread 0x7ffff2679700 (LWP 85) exited]
[Inferior 1 (process 81) exited with code 0107]
(gdb) q

I think, the problem has been located. The "determinize" function in src/fa.c exists a infinite loop, that always alloc the memory... the details as follow:

filename ：fa.c  
functionName: determinize  
lineNumber: 1329 - 1359

   while (worklist != NULL) {
        struct state_set *sset = state_set_list_pop(&worklist);
        struct state *r = state_set_hash_get_state(newstate, sset);
        for (int q=0; q < sset->used; q++) {
            r->accept |= sset->states[q]->accept;
        }
        for (int n=0; n < npoints; n++) {
            struct state_set *pset = state_set_init(-1, S_SORTED);
            E(pset == NULL);
            for(int q=0 ; q < sset->used; q++) {
                for_each_trans(t, sset->states[q]) {
                    if (t->min <= points[n] && points[n] <= t->max) {
                        F(state_set_add(pset, t->to));
                    }
                }
            }
            if (!state_set_hash_contains(newstate, pset)) {
                F(state_set_list_add(&worklist, pset));
                F(state_set_hash_add(&newstate, pset, fa));
            }
            pset = state_set_hash_uniq(newstate, pset);

            struct state *q = state_set_hash_get_state(newstate, pset);
            uchar min = points[n];
            uchar max = UCHAR_MAX;
            if (n+1 < npoints)
                max = points[n+1] - 1;
            if (add_new_trans(r, q, min, max) < 0)
                goto error;
        }
    }

I stuck on this point a lot of time... Please help me. !!o!!

228938596 commented 1 year ago

I met the same problem, how did you solve it?

igalic commented 1 year ago

why is the loop infinite?

xingxing618 commented 1 year ago

I met the same problem in 1.13