✨

vector の配列外参照を検知するために UBSAN および ASAN を競技プログラミングで使う

2024/11/18に公開

Background

AtCoder などの競技プログラミングで手元ではエラーにならないのに提出すると Runtime Error やWrong Error になることがある。

例えば https://atcoder.jp/contests/apg4b/tasks/APG4b_cj の問題で以下のコードを提出すると Runtime Error となる。これは vector が n-1 の長さなのに n-1 番目にアクセスしようとしているからである。しかも厄介なことにすべてのケースで Runtime Error になるわけではなく、いくつかのケースでエラーになる。

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char** argv) {
    int n; cin >> n;

    vector<int> a(n-1); // a を n-1 個の配列にしておく
    for (int i = 0; i < n; i++)
        cin >> a[i]; // i = n-1 のとき配列外参照

    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i]; // i = n-1 のとき配列外参照
    }

    int ave = sum / n;

    for (int i = 0; i < n; i++) {
        cout << abs(a[i] - ave) << endl; // i = n-1 のとき配列外参照
    }
    
    return 0;
}

解決方法

C++ は速度のために vector や配列の operator[] は配列の長さをチェックしないが、 Address Sanitizer (とついでに Undefined Sanitizer) を有効にすることでチェックすることができる。

$ export UBSAN_OPTIONS="print_stacktrace=1:halt_on_error=1"
$ gcc -fsanitize=undefined,address main.cpp
$ ./a.out 
2
80 60
=================================================================
==36896==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x502000000014 at pc 0x559268ca3749 bp 0x7ffd4e4847d0 sp 0x7ffd4e4847c8
READ of size 4 at 0x502000000014 thread T0
    #0 0x559268ca3748 in main /home/tomoki/Dropbox/codes/contest/ubsan/main.cpp:15
    #1 0x7f9f30e33d67  (/lib/x86_64-linux-gnu/libc.so.6+0x29d67) (BuildId: 522aec690df2798fac29fc4608b2c28fd5968271)
    #2 0x7f9f30e33e24 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e24) (BuildId: 522aec690df2798fac29fc4608b2c28fd5968271)
    #3 0x559268ca3210 in _start (/home/tomoki/Dropbox/codes/contest/ubsan/a.out+0x5210) (BuildId: 47a754a735ccbc02de3e6ac5dde87b54bc4b3b8a)

0x502000000014 is located 0 bytes after 4-byte region [0x502000000010,0x502000000014)
allocated by thread T0 here:
    #0 0x7f9f31cf5798 in operator new(unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:95
    #1 0x559268ca5234 in std::__new_allocator<int>::allocate(unsigned long, void const*) /usr/include/c++/14/bits/new_allocator.h:151
    #2 0x559268ca505d in std::allocator_traits<std::allocator<int> >::allocate(std::allocator<int>&, unsigned long) /usr/include/c++/14/bits/alloc_traits.h:509
    #3 0x559268ca505d in std::_Vector_base<int, std::allocator<int> >::_M_allocate(unsigned long) /usr/include/c++/14/bits/stl_vector.h:380
    #4 0x559268ca4aab in std::_Vector_base<int, std::allocator<int> >::_M_create_storage(unsigned long) /usr/include/c++/14/bits/stl_vector.h:398
    #5 0x559268ca4340 in std::_Vector_base<int, std::allocator<int> >::_Vector_base(unsigned long, std::allocator<int> const&) /usr/include/c++/14/bits/stl_vector.h:334
    #6 0x559268ca3d36 in std::vector<int, std::allocator<int> >::vector(unsigned long, std::allocator<int> const&) /usr/include/c++/14/bits/stl_vector.h:557
    #7 0x559268ca34ec in main /home/tomoki/Dropbox/codes/contest/ubsan/main.cpp:9
    #8 0x7f9f30e33d67  (/lib/x86_64-linux-gnu/libc.so.6+0x29d67) (BuildId: 522aec690df2798fac29fc4608b2c28fd5968271)

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/tomoki/Dropbox/codes/contest/ubsan/main.cpp:15 in main
Shadow bytes around the buggy address:
  0x501ffffffd80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501ffffffe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501ffffffe80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501fffffff00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501fffffff80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x502000000000: fa fa[04]fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000200: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000280: 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
==36896==ABORTING

CMake を使っている場合は以下のようにデバッグ時のみ有効にするのがよいかもしれない。 (実際のプロダクトではむしろリリース時に有効にしたい機能ではある。 UB や不正なアドレス参照が直接脆弱性につながる前に落としたいため)

set (CMAKE_CXX_STANDARD 20)
if (MSVC)
    set(CMAKE_CXX_FLAGS_DEBUG "/fsanitize=address")
else()
    set(CMAKE_CXX_FLAGS_DEBUG "-fsanitize=undefined,address")
endif()

Background

解決方法

Discussion