当我运行我的c代码时,我的解决方案是
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 1000
int isValid(char* curStr) {
char* ptr = curStr;
int leftCount = 0;
while (*ptr != '\0') {
if (*ptr == '(') {
leftCount++;
} else { // *ptr == ')'
leftCount--;
}
if (leftCount < 0) {
return 0;
}
ptr++;
}
return leftCount == 0;
}
void generateParenthesisRecursive(char* curStr, int curStrLen, int n, int* returnSize, char** res) {
// exit condition of recursive
if (curStrLen == 2 * n) {
if (isValid(curStr)) {
res[(*returnSize)] = (char *) malloc(sizeof(char) * (curStrLen + 1));
strcpy(res[(*returnSize)], curStr);
(*returnSize)++;
}
return;
}
// iterate recursively
char* curStrNewLeft = (char *) malloc(sizeof(char) * (curStrLen + 2));
char* curStrNewRight = (char *) malloc(sizeof(char) * (curStrLen + 2));
strcat(curStrNewLeft, curStr);
strcat(curStrNewLeft, "(");
strcat(curStrNewRight, curStr);
strcat(curStrNewRight, ")");
generateParenthesisRecursive(curStrNewLeft, curStrLen + 1, n, returnSize, res);
generateParenthesisRecursive(curStrNewRight, curStrLen + 1, n, returnSize, res);
}
char ** generateParenthesisV2(int n, int* returnSize){
// initialize *returnSize to zero
*returnSize = 0;
// create final return result
char** res = (char **) malloc(sizeof(char *) * MAX_LEN);
char* curStr = (char *) malloc(sizeof(char) * 1);
curStr[0] = '\0';
generateParenthesisRecursive(curStr, 0, n, returnSize, res);
return res;
}
字符串
然后我执行gccbuild命令并运行二进制文件
gcc -fsanitize=address -o ${OUTPUT_BUILD_FILE_PATH} ${MAIN_FILE_PATH}
./${MAIN_FILE_PATH}
型
我得到的堆缓冲区溢出信息如下:
GenerateParentheses_Task22-main(7574,0x7ff84ea6f640) malloc: nano zone abandoned due to inability to reserve vm space.
=================================================================
==7574==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000000d2 at pc 0x0001064c1e77 bp 0x7ff7b9e17dc0 sp 0x7ff7b9e17568
WRITE of size 1 at 0x6020000000d2 thread T0
#0 0x1064c1e76 in wrap_strcat+0x426 (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x42e76) (BuildId: 756bb7515781379f84412f22c4274ffd2400000010000000000a0a0000030d00)
#1 0x1060e9bb3 in generateParenthesisRecursive+0x223 (GenerateParentheses_Task22-main:x86_64+0x100002bb3) (BuildId: f1d1bd488ca8367a9d17ae1d6b27c6c732000000200000000100000000000d00)
#2 0x1060e9cfd in generateParenthesisV2+0xdd (GenerateParentheses_Task22-main:x86_64+0x100002cfd) (BuildId: f1d1bd488ca8367a9d17ae1d6b27c6c732000000200000000100000000000d00)
#3 0x1060ea9aa in main+0x7a (GenerateParentheses_Task22-main:x86_64+0x1000039aa) (BuildId: f1d1bd488ca8367a9d17ae1d6b27c6c732000000200000000100000000000d00)
#4 0x7ff80b03941e in start+0x76e (dyld:x86_64+0xfffffffffff6e41e) (BuildId: 9e98a840a3ac31c1ab97829af9bd686432000000200000000100000000040d00)
0x6020000000d2 is located 0 bytes to the right of 2-byte region [0x6020000000d0,0x6020000000d2)
allocated by thread T0 here:
#0 0x1064c7da0 in wrap_malloc+0xa0 (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x48da0) (BuildId: 756bb7515781379f84412f22c4274ffd2400000010000000000a0a0000030d00)
#1 0x1060e9b8c in generateParenthesisRecursive+0x1fc (GenerateParentheses_Task22-main:x86_64+0x100002b8c) (BuildId: f1d1bd488ca8367a9d17ae1d6b27c6c732000000200000000100000000000d00)
#2 0x1060e9cfd in generateParenthesisV2+0xdd (GenerateParentheses_Task22-main:x86_64+0x100002cfd) (BuildId: f1d1bd488ca8367a9d17ae1d6b27c6c732000000200000000100000000000d00)
#3 0x1060ea9aa in main+0x7a (GenerateParentheses_Task22-main:x86_64+0x1000039aa) (BuildId: f1d1bd488ca8367a9d17ae1d6b27c6c732000000200000000100000000000d00)
#4 0x7ff80b03941e in start+0x76e (dyld:x86_64+0xfffffffffff6e41e) (BuildId: 9e98a840a3ac31c1ab97829af9bd686432000000200000000100000000040d00)
SUMMARY: AddressSanitizer: heap-buffer-overflow (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x42e76) (BuildId: 756bb7515781379f84412f22c4274ffd2400000010000000000a0a0000030d00) in wrap_strcat+0x426
Shadow bytes around the buggy address:
0x1c03ffffffc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1c03ffffffd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1c03ffffffe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1c03fffffff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1c0400000000: fa fa fd fd fa fa 00 00 fa fa 00 00 fa fa 00 06
=>0x1c0400000010: fa fa 00 00 fa fa 01 fa fa fa[02]fa fa fa 02 fa
0x1c0400000020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x1c0400000030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x1c0400000040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x1c0400000050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x1c0400000060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
==7574==ABORTING
[1] 7574 abort ./DynamicProgramming/22-Generate_Parentheses/C/GenerateParentheses_Task22-mai
型
有人能帮我解决这个问题吗?我花了大约1个小时来弄清楚这一点,但它没有工作。顺便问一下,我可以使用什么方法来调试更有效地定位堆缓冲区溢出?
--分割线--
感谢@Weather Vane,@Whozcry和@Jim莫里森的建议,最好初始化malloc分配的块,所以我在这些更改中优化了我的代码:
1.直接将空字符串“”和curStrLen(0)传递给开头的递归函数
1.在初始化时用malloc替换calloc
1.当curStrLen大于零时释放每个curStr(当curStrLen等于零时,初始空字符串不能释放,因为它不是由malloc分配的)
1.使用strcpy(curStrNewLeft, curStr)
代替strcat(curStrNewLeft, curStr)
更新后的代码为:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 1000
int isValid(char* curStr) {
char* ptr = curStr;
int leftCount = 0;
while (*ptr != '\0') {
if (*ptr == '(') {
leftCount++;
} else { // *ptr == ')'
leftCount--;
}
if (leftCount < 0) {
return 0;
}
ptr++;
}
return leftCount == 0;
}
void generateParenthesisRecursive(char* curStr, int curStrLen, int n, int* returnSize, char** res) {
// exit condition of recursive
if (curStrLen == 2 * n) {
if (isValid(curStr)) {
res[(*returnSize)] = (char *) calloc(curStrLen + 1, sizeof(char));
strcpy(res[(*returnSize)], curStr);
(*returnSize)++;
}
return;
}
// iterate recursively
char* curStrNewLeft = (char *) calloc(curStrLen + 2, sizeof(char));
strcpy(curStrNewLeft, curStr);
strcat(curStrNewLeft, "(");
char* curStrNewRight = (char *) calloc(curStrLen + 2, sizeof(char));
strcpy(curStrNewRight, curStr);
strcat(curStrNewRight, ")");
if (curStrLen > 0) {
free(curStr);
}
generateParenthesisRecursive(curStrNewLeft, curStrLen + 1, n, returnSize, res);
generateParenthesisRecursive(curStrNewRight, curStrLen + 1, n, returnSize, res);
}
char ** generateParenthesisV2(int n, int* returnSize){
// initialize *returnSize to zero
*returnSize = 0;
// create final return result
char** res = (char **) malloc(sizeof(char *) * MAX_LEN);
generateParenthesisRecursive("", 0, n, returnSize, res);
return res;
}
型
在我的mac上,一切都可以用clion运行,但是当我用gcc将它构建为二进制文件来运行时,我仍然遇到了堆缓冲区溢出问题,然后我使用@Whozcry推荐给我的valgrind:valgrind --leak-check=full ./GenerateParentheses_Task22-main
输出为:
==39646== Memcheck, a memory error detector
==39646== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==39646== Using Valgrind-3.22.0.GIT-lbmacos and LibVEX; rerun with -h for copyright info
==39646== Command: ./GenerateParentheses_Task22-main
==39646==
==39646== Syscall param map_with_linking_np(link_info) points to uninitialised byte(s)
==39646== at 0x10007BE32: __map_with_linking_np (in /usr/lib/dyld)
==39646== by 0x10002BE4D: dyld4::setUpPageInLinkingRegions(dyld4::RuntimeState&, dyld4::Loader const*, unsigned long, unsigned short, unsigned short, bool, dyld3::Array<dyld4::PageInLinkingRange> const&, dyld3::Array<void const*> const&) (in /usr/lib/dyld)
==39646== by 0x10002B820: invocation function for block in dyld4::Loader::setUpPageInLinking(Diagnostics&, dyld4::RuntimeState&, unsigned long, unsigned long long, dyld3::Array<void const*> const&) const (in /usr/lib/dyld)
==39646== by 0x10002B5A4: dyld4::Loader::setUpPageInLinking(Diagnostics&, dyld4::RuntimeState&, unsigned long, unsigned long long, dyld3::Array<void const*> const&) const (in /usr/lib/dyld)
==39646== by 0x10002BFCA: dyld4::Loader::applyFixupsGeneric(Diagnostics&, dyld4::RuntimeState&, unsigned long long, dyld3::Array<void const*> const&, dyld3::Array<void const*> const&, bool, dyld3::Array<dyld4::Loader::MissingFlatLazySymbol> const&) const (in /usr/lib/dyld)
==39646== by 0x100031268: dyld4::JustInTimeLoader::applyFixups(Diagnostics&, dyld4::RuntimeState&, dyld4::DyldCacheDataConstLazyScopedWriter&, bool) const (in /usr/lib/dyld)
==39646== by 0x1000172A4: dyld4::prepare(dyld4::APIs&, dyld3::MachOAnalyzer const*) (in /usr/lib/dyld)
==39646== by 0x1000163BC: (below main) (in /usr/lib/dyld)
==39646== Address 0x10490c910 is on thread 1's stack
==39646== in frame #1, created by dyld4::setUpPageInLinkingRegions(dyld4::RuntimeState&, dyld4::Loader const*, unsigned long, unsigned short, unsigned short, bool, dyld3::Array<dyld4::PageInLinkingRange> const&, dyld3::Array<void const*> const&) (???:)
==39646==
==39646== Conditional jump or move depends on uninitialised value(s)
==39646== at 0x7FF80B359120: ???
==39646== by 0x7FF80B25BBBF: _init_clock_port (in /usr/lib/system/libsystem_c.dylib)
==39646== by 0x7FF80B25BAA3: _libc_initializer (in /usr/lib/system/libsystem_c.dylib)
==39646== by 0x7FF8171F7846: libSystem_initializer (in /usr/lib/libSystem.B.dylib)
==39646== by 0x10002F41A: invocation function for block in dyld4::Loader::findAndRunAllInitializers(dyld4::RuntimeState&) const::$_0::operator()() const (in /usr/lib/dyld)
==39646== by 0x10006DB69: invocation function for block in dyld3::MachOAnalyzer::forEachInitializer(Diagnostics&, dyld3::MachOAnalyzer::VMAddrConverter const&, void ( block_pointer)(unsigned int), void const*) const (in /usr/lib/dyld)
==39646== by 0x100061F21: invocation function for block in dyld3::MachOFile::forEachSection(void ( block_pointer)(dyld3::MachOFile::SectionInfo const&, bool, bool&)) const (in /usr/lib/dyld)
==39646== by 0x1000120AE: dyld3::MachOFile::forEachLoadCommand(Diagnostics&, void ( block_pointer)(load_command const*, bool&)) const (in /usr/lib/dyld)
==39646== by 0x1000610BE: dyld3::MachOFile::forEachSection(void ( block_pointer)(dyld3::MachOFile::SectionInfo const&, bool, bool&)) const (in /usr/lib/dyld)
==39646== by 0x10006D729: dyld3::MachOAnalyzer::forEachInitializer(Diagnostics&, dyld3::MachOAnalyzer::VMAddrConverter const&, void ( block_pointer)(unsigned int), void const*) const (in /usr/lib/dyld)
==39646== by 0x10002C68B: dyld4::Loader::findAndRunAllInitializers(dyld4::RuntimeState&) const (in /usr/lib/dyld)
==39646== by 0x1000351F3: dyld4::PrebuiltLoader::runInitializers(dyld4::RuntimeState&) const (in /usr/lib/dyld)
==39646==
==39646== Warning: set address range perms: large range [0xffffffff000, 0x120000000000) (defined)
==39646== Warning: set address range perms: large range [0x140000000000, 0x200000000000) (defined)
==39646== Warning: set address range perms: large range [0x120000000000, 0x140000000000) (noaccess)
==39646== Warning: set address range perms: large range [0x600000000000, 0x640000002000) (noaccess)
GenerateParentheses_Task22-main(39646,0x1000b8280) malloc: nano zone abandoned due to inability to reserve vm space.
==39646== Syscall param socketcall.sendto(msg) points to uninitialised byte(s)
==39646== at 0x7FF80B357C2E: ???
==39646== by 0x1005078C6: wrap_dlclose (in /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/clang/14.0.3/lib/darwin/libclang_rt.asan_osx_dynamic.dylib)
==39646== by 0x7FF80B3C1C35: ???
==39646== by 0x7FF80B3C1AC6: ???
==39646== by 0x7FF80B3C1D67: ???
==39646== by 0x7FF80B1D05F8: malloc_vreport (in /usr/lib/system/libsystem_malloc.dylib)
==39646== by 0x7FF80B1D3B30: malloc_report (in /usr/lib/system/libsystem_malloc.dylib)
==39646== by 0x7FF80B1D2D2A: nanov2_create_zone (in /usr/lib/system/libsystem_malloc.dylib)
==39646== by 0x7FF80B1D1C99: __malloc_init (in /usr/lib/system/libsystem_malloc.dylib)
==39646== by 0x7FF8171F7859: libSystem_initializer (in /usr/lib/libSystem.B.dylib)
==39646== by 0x10002F41A: invocation function for block in dyld4::Loader::findAndRunAllInitializers(dyld4::RuntimeState&) const::$_0::operator()() const (in /usr/lib/dyld)
==39646== by 0x10006DB69: invocation function for block in dyld3::MachOAnalyzer::forEachInitializer(Diagnostics&, dyld3::MachOAnalyzer::VMAddrConverter const&, void ( block_pointer)(unsigned int), void const*) const (in /usr/lib/dyld)
==39646== Address 0x10490c625 is on thread 1's stack
==39646==
==39646== Invalid read of size 1
==39646== at 0x1004D0A06: ??? (in /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/clang/14.0.3/lib/darwin/libclang_rt.asan_osx_dynamic.dylib)
==39646== by 0x100514F4D: __wrap_dispatch_after_block_invoke (in /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/clang/14.0.3/lib/darwin/libclang_rt.asan_osx_dynamic.dylib)
==39646== by 0x7FF80AFFBD87: _NXHashRehashToCapacity (in /usr/lib/libobjc.A.dylib)
==39646== by 0x7FF80AFFBCB1: NXHashInsert (in /usr/lib/libobjc.A.dylib)
==39646== by 0x7FF80AFFB97D: NXCreateHashTableFromZone (in /usr/lib/libobjc.A.dylib)
==39646== by 0x7FF80AFFB761: NXCreateMapTableFromZone (in /usr/lib/libobjc.A.dylib)
==39646== by 0x7FF80AFFA2DB: map_images_nolock (in /usr/lib/libobjc.A.dylib)
==39646== by 0x7FF80AFF960E: map_images (in /usr/lib/libobjc.A.dylib)
==39646== by 0x10002575F: invocation function for block in dyld4::RuntimeState::setObjCNotifiers(void (*)(unsigned int, char const* const*, mach_header const* const*), void (*)(char const*, mach_header const*), void (*)(char const*, mach_header const*), void (*)(mach_header const*, void*, mach_header const*, void const*), void (*)(unsigned int, _dyld_objc_notify_mapped_info const*))::$_8::operator()() const (in /usr/lib/dyld)
==39646== by 0x10001D6F8: dyld4::RuntimeState::withLoadersReadLock(void ( block_pointer)()) (in /usr/lib/dyld)
==39646== by 0x1000225FA: dyld4::RuntimeState::setObjCNotifiers(void (*)(unsigned int, char const* const*, mach_header const* const*), void (*)(char const*, mach_header const*), void (*)(char const*, mach_header const*), void (*)(mach_header const*, void*, mach_header const*, void const*), void (*)(unsigned int, _dyld_objc_notify_mapped_info const*)) (in /usr/lib/dyld)
==39646== by 0x100048187: dyld4::APIs::_dyld_objc_register_callbacks(_dyld_objc_callbacks const*) (in /usr/lib/dyld)
==39646== Address 0x1027001a0 is 16 bytes before a block of size 24 alloc'd
==39646== at 0x10017B856: malloc_zone_calloc (in /usr/local/Cellar/valgrind/HEAD-8c360fc/libexec/valgrind/vgpreload_memcheck-amd64-darwin.so)
==39646== by 0x7FF80AFFBC77: NXHashInsert (in /usr/lib/libobjc.A.dylib)
==39646== by 0x7FF80AFFB97D: NXCreateHashTableFromZone (in /usr/lib/libobjc.A.dylib)
==39646== by 0x7FF80AFFB761: NXCreateMapTableFromZone (in /usr/lib/libobjc.A.dylib)
==39646== by 0x7FF80AFFA2DB: map_images_nolock (in /usr/lib/libobjc.A.dylib)
==39646== by 0x7FF80AFF960E: map_images (in /usr/lib/libobjc.A.dylib)
==39646== by 0x10002575F: invocation function for block in dyld4::RuntimeState::setObjCNotifiers(void (*)(unsigned int, char const* const*, mach_header const* const*), void (*)(char const*, mach_header const*), void (*)(char const*, mach_header const*), void (*)(mach_header const*, void*, mach_header const*, void const*), void (*)(unsigned int, _dyld_objc_notify_mapped_info const*))::$_8::operator()() const (in /usr/lib/dyld)
==39646== by 0x10001D6F8: dyld4::RuntimeState::withLoadersReadLock(void ( block_pointer)()) (in /usr/lib/dyld)
==39646== by 0x1000225FA: dyld4::RuntimeState::setObjCNotifiers(void (*)(unsigned int, char const* const*, mach_header const* const*), void (*)(char const*, mach_header const*), void (*)(char const*, mach_header const*), void (*)(mach_header const*, void*, mach_header const*, void const*), void (*)(unsigned int, _dyld_objc_notify_mapped_info const*)) (in /usr/lib/dyld)
==39646== by 0x100048187: dyld4::APIs::_dyld_objc_register_callbacks(_dyld_objc_callbacks const*) (in /usr/lib/dyld)
==39646== by 0x7FF80AFF90CE: _objc_init (in /usr/lib/libobjc.A.dylib)
==39646== by 0x7FF80B1F16A8: _os_object_init (in /usr/lib/system/libdispatch.dylib)
==39646==
=================================================================
==39646==ERROR: AddressSanitizer: attempting free on address which was not malloc()-ed: 0x0001027001b0 in thread T0
==39646== Warning: invalid file descriptor -1 in syscall close()
==39646==WARNING: Can't read from symbolizer at fd 5
==39646== Warning: invalid file descriptor -1 in syscall close()
==39646==WARNING: Can't read from symbolizer at fd 6
==39646== Warning: invalid file descriptor -1 in syscall close()
==39646==WARNING: Can't read from symbolizer at fd 7
==39646== Warning: invalid file descriptor -1 in syscall close()
==39646==WARNING: Can't read from symbolizer at fd 8
==39646== Warning: invalid file descriptor -1 in syscall close()
==39646==WARNING: Failed to use and restart external symbolizer!
#0 0x100514ee9 in wrap_free+0xa9 (/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/clang/14.0.3/lib/darwin/libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x48ee9) (BuildId: 756bb7515781379f84412f22c4274ffd2400000010000000000a0a0000030d00)
#1 0x7ff80affbd87 in _NXHashRehashToCapacity+0xc4 (/usr/lib/libobjc.A.dylib:x86_64h+0x4d87) (BuildId: 4fc61ea7873735738d14f8f342b438aa32000000200000000100000000040d00)
#2 0x7ff80affbcb1 in NXHashInsert+0x18a (/usr/lib/libobjc.A.dylib:x86_64h+0x4cb1) (BuildId: 4fc61ea7873735738d14f8f342b438aa32000000200000000100000000040d00)
#3 0x7ff80affb97d in NXCreateHashTableFromZone+0x115 (/usr/lib/libobjc.A.dylib:x86_64h+0x497d) (BuildId: 4fc61ea7873735738d14f8f342b438aa32000000200000000100000000040d00)
#4 0x7ff80affb761 in NXCreateMapTableFromZone+0x56 (/usr/lib/libobjc.A.dylib:x86_64h+0x4761) (BuildId: 4fc61ea7873735738d14f8f342b438aa32000000200000000100000000040d00)
#5 0x7ff80affa2db in map_images_nolock+0xc52 (/usr/lib/libobjc.A.dylib:x86_64h+0x32db) (BuildId: 4fc61ea7873735738d14f8f342b438aa32000000200000000100000000040d00)
#6 0x7ff80aff960e in map_images+0x42 (/usr/lib/libobjc.A.dylib:x86_64h+0x260e) (BuildId: 4fc61ea7873735738d14f8f342b438aa32000000200000000100000000040d00)
#7 0x10002575f (<unknown module>)
#8 0x10001d6f8 (<unknown module>)
#9 0x1000225fa (<unknown module>)
#10 0x100048187 (<unknown module>)
#11 0x7ff80aff90ce in _objc_init+0x24a (/usr/lib/libobjc.A.dylib:x86_64h+0x20ce) (BuildId: 4fc61ea7873735738d14f8f342b438aa32000000200000000100000000040d00)
#12 0x7ff80b1f16a8 in _os_object_init+0xc (/usr/lib/system/libdispatch.dylib:x86_64+0x26a8) (BuildId: da7432300aca3094821c5e1565d8b18732000000200000000100000000040d00)
#13 0x7ff80b1ff566 in libdispatch_init+0x16a (/usr/lib/system/libdispatch.dylib:x86_64+0x10566) (BuildId: da7432300aca3094821c5e1565d8b18732000000200000000100000000040d00)
#14 0x7ff8171f7897 in libSystem_initializer+0xed (/usr/lib/libSystem.B.dylib:x86_64+0x1897) (BuildId: 65c3ab0214233a369e9388bc046941d832000000200000000100000000040d00)
#15 0x10002f41a (<unknown module>)
#16 0x10006db69 (<unknown module>)
#17 0x100061f21 (<unknown module>)
#18 0x1000120ae (<unknown module>)
#19 0x1000610be (<unknown module>)
#20 0x10006d729 (<unknown module>)
#21 0x10002c68b (<unknown module>)
#22 0x1000351f3 (<unknown module>)
#23 0x10004dbdc (<unknown module>)
#24 0x100017873 (<unknown module>)
#25 0x1000163bc (<unknown module>)
Address 0x0001027001b0 is a wild pointer inside of access range of size 0x000000000001.
SUMMARY: AddressSanitizer: bad-free (/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/clang/14.0.3/lib/darwin/libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x48ee9) (BuildId: 756bb7515781379f84412f22c4274ffd2400000010000000000a0a0000030d00) in wrap_free+0xa9
==39646== Invalid read of size 4
==39646== at 0x7FF80AFFE2E4: class_createInstance (in /usr/lib/libobjc.A.dylib)
==39646== by 0x7FF80B1F1746: _os_object_alloc_realized (in /usr/lib/system/libdispatch.dylib)
==39646== by 0x7FF80B0D4D22: xpc_bundle_create_from_origin (in /usr/lib/system/libxpc.dylib)
==39646== by 0x7FF80B0D861B: xpc_bundle_create_main (in /usr/lib/system/libxpc.dylib)
==39646== by 0x7FF80B112CCC: _os_trace_init_slow (in /usr/lib/system/libsystem_trace.dylib)
==39646== by 0x7FF80B1F2032: _dispatch_client_callout (in /usr/lib/system/libdispatch.dylib)
==39646== by 0x7FF80B1F3266: _dispatch_once_callout (in /usr/lib/system/libdispatch.dylib)
==39646== by 0x7FF80B11F5B0: _os_trace_with_buffer (in /usr/lib/system/libsystem_trace.dylib)
==39646== by 0x100530D76: __sanitizer::GetRSS() (in /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/clang/14.0.3/lib/darwin/libclang_rt.asan_osx_dynamic.dylib)
==39646== by 0x10051DC6F: __asan::ScopedInErrorReport::~ScopedInErrorReport() (in /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/clang/14.0.3/lib/darwin/libclang_rt.asan_osx_dynamic.dylib)
==39646== by 0x10051A89E: __asan::ReportFreeNotMalloced(unsigned long, __sanitizer::BufferedStackTrace*) (in /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/clang/14.0.3/lib/darwin/libclang_rt.asan_osx_dynamic.dylib)
==39646== by 0x100514F4D: __wrap_dispatch_after_block_invoke (in /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/clang/14.0.3/lib/darwin/libclang_rt.asan_osx_dynamic.dylib)
==39646== Address 0x10 is not stack'd, malloc'd or (recently) free'd
==39646==
AddressSanitizer:DEADLYSIGNAL
AddressSanitizer: nested bug in the same thread, aborting.
==39646==
==39646== HEAP SUMMARY:
==39646== in use at exit: 208 bytes in 7 blocks
==39646== total heap usage: 7 allocs, 0 frees, 208 bytes allocated
==39646==
[1] 39646 killed valgrind --leak-check=full ./GenerateParentheses_Task22-main
型
我是Valgrind的新手,所以我搜索了文档并在日志中列出了一些关键点:
1.“Syscall param map_with_linking_np(link_info)points to uninitialised byte(s)”可能是由于使用了未初始化的内存,但所有分配的都是由calloc创建的
1.“使用指向超出范围的局部变量的指针”可能是由于“使用指向超出范围的局部变量的指针”或“在缓冲区超出范围后使用指向堆栈分配的缓冲区的指针”
1.“条件转移或移动依赖于未初始化的值”可能是由程序中依赖于未初始化变量值的条件分支或移动指令引起的
但我仍然不清楚究竟是什么问题。你能帮我弄明白吗?真不知道下一步该怎么办。:(
当然,@Whozcry的解决方案在这些方面肯定更好:
1.这是一个回溯版本,删除无用的案例以保存时间
1.它使用全局变量char* stack
,而不是在每个递归级别中分配块。
,但我只是想更好地理解堆缓冲区溢出问题,因为我在很多场景中都遇到过这种情况。我将采取回溯版本或dp版本的解决方案,但在此之后堆缓冲区溢出的位置。:(
2条答案
按热度按时间sqxo8psd1#
我认为你的程序有太多的
malloc
,没有free
,所以它会导致内存泄漏。下面是我的答案,因为the link
Constraints: 1 <= n <= 8
,所以我测试n = 8。字符串
运行它将输出:
型
为了更有效地调试堆缓冲区溢出,请在此链接查看我对Valgrind使用问题的回答。
更新
使用命令时:
型
输出的最后一部分:
型
展示
型
你只分配内存(7 allocs),但没有
free
(0 frees)。所以在你更新的代码中可能没有
free
的错误是:型
和/或
型
可能是错误。
我认为你更新的代码有很多问题。如果可能的话,我建议使用我的代码。
cbjzeqam2#
malloc
返回指向未初始化内存的指针。在迭代的情况下,当你strcat
到这个新分配的块时,它可能会溢出,因为它可能全是1,只有最后一个字符是nul-terminator。要解决此问题,请使用
calloc
,将\0
分配给第一个字符,或使用strcpy