logo
ZirAjs
logo

카테고리 목록  

[Rev] Cpp Vector analysis

Study
2025. 8. 6.

Introduction

Dreamhack의 Photographer 문제에 필요한 cpp STL에 대해 공부했다. 이를 위해 코드를 작성하고 컴파일과 디컴파일 과정을 통해 어떻게 코드가 컴파일되는지 공부했다. 이번 포스트에서는 std::vector 만 다루었다.

Compile / Decompile result

#include <bits/stdc++.h>

int main()
{
    int temp;
    std::cout << "This program helps basic understanding of c++ program" << std::endl;

    std::cout << "Below codes are initialization of vector" << std::endl;
    std::vector<int> x{0, 1, 2, 3, 4, 5, 6};
    std::cout << "push" << std::endl;
    x.push_back(7);
    x.pop_back();
    temp = x.at(1);

    for (auto i = x.begin(); i < x.end(); i++)
    {
        temp = (*i);
    }

    for (auto i : x)
    {
        temp = i;
    }

    std::cout << "Below codes are initialization of plain C array" << std::endl;
    int y[] = {0, 1, 2, 3, 4, 5, 6};
    temp = y[sizeof(y) / sizeof(y[0])];

    std::cout << "Below codes are initialization of plain Cpp array" << std::endl;
    std::array<int, 7> z{0, 1, 2, 3, 4, 5, 6};
    temp = z[0];

    std::cout << "Below codes are initialization of plain Cpp list" << std::endl;
    std::list<int> w{0, 1, 2, 3, 4, 5, 6};
    w.push_back(7);
    w.push_front(8);

    for (auto i : w)
    {
        temp = i;
    }

    return 0;
}

g++ ./analysis.cpp -o analysis
cp ./analysis analysis_stripped
strip --strip-all ./analysis_stripped

int __fastcall main(int argc, const char **argv, const char **envp)
{
  __int64 v3; // rax
  __int64 v4; // rdx
  __int64 v5; // rax
  __int64 v6; // rdx
  __int64 v7; // rax
  __int64 v8; // rdx
  __int64 v9; // rax
  __int64 v10; // rdx
  __int64 v11; // rax
  __int64 v12; // rdx
  __int64 v13; // rax
  __int64 v15; // [rsp+8h] [rbp-128h] BYREF
  __int64 v16; // [rsp+10h] [rbp-120h] BYREF
  __int64 v17; // [rsp+18h] [rbp-118h] BYREF
  __int64 v18; // [rsp+20h] [rbp-110h] BYREF
  __int64 i; // [rsp+28h] [rbp-108h] BYREF
  _BYTE v20[32]; // [rsp+30h] [rbp-100h] BYREF
  _DWORD v21[16]; // [rsp+50h] [rbp-E0h] BYREF
  _BYTE v22[35]; // [rsp+90h] [rbp-A0h] BYREF
  char v23; // [rsp+B3h] [rbp-7Dh] BYREF
  int v24; // [rsp+B4h] [rbp-7Ch] BYREF
  __int64 v25; // [rsp+B8h] [rbp-78h] BYREF
  char v26; // [rsp+C7h] [rbp-69h] BYREF
  int v27; // [rsp+C8h] [rbp-68h] BYREF
  int v28; // [rsp+CCh] [rbp-64h] BYREF
  char *v29; // [rsp+D0h] [rbp-60h]
  char *v30; // [rsp+D8h] [rbp-58h]
  int v31; // [rsp+E0h] [rbp-50h]
  int v32; // [rsp+E4h] [rbp-4Ch]
  _BYTE *v33; // [rsp+E8h] [rbp-48h]
  _BYTE *v34; // [rsp+F0h] [rbp-40h]
  int v35; // [rsp+FCh] [rbp-34h]

  v3 = std::operator<<<std::char_traits<char>>(
         &_bss_start,
         "This program helps basic understanding of c++ program",
         envp);
  std::ostream::operator<<(v3, &std::endl<char,std::char_traits<char>>);
  v5 = std::operator<<<std::char_traits<char>>(&_bss_start, "Below codes are initialization of vector", v4);
  std::ostream::operator<<(v5, &std::endl<char,std::char_traits<char>>);
  v30 = &v23;
  std::vector<int>::vector(v22, &C_0_0, 7, &v23);
  std::__new_allocator<int>::~__new_allocator(&v23);
  v7 = std::operator<<<std::char_traits<char>>(&_bss_start, "push", v6);
  std::ostream::operator<<(v7, &std::endl<char,std::char_traits<char>>);
  v24 = 7;
  std::vector<int>::push_back(v22, &v24);
  std::vector<int>::pop_back(v22);
  v35 = *(_DWORD *)std::vector<int>::at(v22, 1);
  for ( i = std::vector<int>::begin(v22); ; __gnu_cxx::__normal_iterator<int *,std::vector<int>>::operator++(&i, 0) )
  {
    v25 = std::vector<int>::end(v22);
    if ( !(unsigned __int8)__gnu_cxx::operator<<int *,std::vector<int>>(&i, &v25) )
      break;
    v35 = *(_DWORD *)__gnu_cxx::__normal_iterator<int *,std::vector<int>>::operator*(&i);
  }
  v34 = v22;
  v18 = std::vector<int>::begin(v22);
  v17 = std::vector<int>::end(v34);
  while ( (unsigned __int8)__gnu_cxx::operator!=<int *,std::vector<int>>(&v18, &v17) )
  {
    v31 = *(_DWORD *)__gnu_cxx::__normal_iterator<int *,std::vector<int>>::operator*(&v18);
    v35 = v31;
    __gnu_cxx::__normal_iterator<int *,std::vector<int>>::operator++(&v18);
  }
  v9 = std::operator<<<std::char_traits<char>>(&_bss_start, "Below codes are initialization of plain C array", v8);
  std::ostream::operator<<(v9, &std::endl<char,std::char_traits<char>>);
  v21[8] = 0;
  v21[9] = 1;
  v21[10] = 2;
  v21[11] = 3;
  v21[12] = 4;
  v21[13] = 5;
  v21[14] = 6;
  v35 = v21[15];
  v11 = std::operator<<<std::char_traits<char>>(&_bss_start, "Below codes are initialization of plain Cpp array", v10);
  std::ostream::operator<<(v11, &std::endl<char,std::char_traits<char>>);
  v21[0] = 0;
  v21[1] = 1;
  v21[2] = 2;
  v21[3] = 3;
  v21[4] = 4;
  v21[5] = 5;
  v21[6] = 6;
  v35 = *(_DWORD *)std::array<int,7ul>::operator[](v21, 0);
  v13 = std::operator<<<std::char_traits<char>>(&_bss_start, "Below codes are initialization of plain Cpp list", v12);
  std::ostream::operator<<(v13, &std::endl<char,std::char_traits<char>>);
  v29 = &v26;
  std::list<int>::list(v20, &C_3_1, 7, &v26);
  std::__new_allocator<int>::~__new_allocator(&v26);
  v27 = 7;
  std::list<int>::push_back(v20, &v27);
  v28 = 8;
  std::list<int>::push_front(v20, &v28);
  v33 = v20;
  v16 = std::list<int>::begin(v20);
  v15 = std::list<int>::end(v33);
  while ( (unsigned __int8)std::operator!=(&v16, &v15) )
  {
    v32 = *(_DWORD *)std::_List_iterator<int>::operator*(&v16);
    v35 = v32;
    std::_List_iterator<int>::operator++(&v16);
  }
  std::list<int>::~list(v20);
  std::vector<int>::~vector(v22);
  return 0;
}

Analysis

이번 분석에서 std::vector에 집중해서 분석을 하고자 한다. 그러기에 앞서 이 분석은 comiler option에서 optimization이 없다는 것에 유의할 필요가 있다.

Constructor

std::vector를 생성하면

// C_0_0은 {0,1,2,3,..,6}이 정의된 위치
std::vector<int>::vector(v22, &C_0_0, 7, &v23);

위 함수를 실행한다. 그리고 정의를 살펴보면,

__int64 __fastcall std::vector<int>::vector(__int64 a1, __int64 a2, __int64 a3, __int64 a4, __int64 a5, __int64 a6)
{
  __int64 v6; // rbx
  __int64 v7; // rax
  __int64 v9; // [rsp+0h] [rbp-40h] BYREF
  __int64 v10; // [rsp+18h] [rbp-28h]

  v10 = a1;
  std::_Vector_base<int>::_Vector_base(a1, a4, a4, a4, a5, a6, a2, a3, a4);
  v6 = std::initializer_list<int>::end(&v9);
  v7 = std::initializer_list<int>::begin(&v9);
  return std::vector<int>::_M_range_initialize<int const*>(v10, v7, v6);
}

위와 같다. 전반적인 흐름은 memory setup > begin/end setup > initialize로 진행된다. 먼저 _Vector_base부터 보자면, 실제 구현은 아래처럼 1개(또는 2개)의 인자만 사용해서 vector가 담는 포인터들을 초기화 한다.

_QWORD *__fastcall std::_Vector_base<int>::_Vector_impl_data::_Vector_impl_data(_QWORD *a1)
{
  _QWORD *result; // rax
  *a1 = 0;
  a1[1] = 0;
  result = a1;
  a1[2] = 0;
  return result;
}

컴파일러마다 다르지만, 일반적으로 아래처럼 vector가 정의된다.

template<typename T, typename Allocator = std::allocator<T>>
class _Vector_base {
protected:
    T* _M_start;
    T* _M_finish;
    T* _M_end_of_storage;
    Allocator _M_alloc;

public:
    _Vector_base(size_t n, const Allocator& alloc);
    // ...
};

여기서 _M_start, _M_finish, _M_end_of_storage을 _Vector_base가 초기화해주는 것이다. 앞선 코드에서는 모두 0으로 초기화 해주었는데, 이후 begin, end를 초기화 하면 제대로 설정된다.

마지막 std::vector<int>::_M_range_initialize<int const*>(v10, v7, v6);에서는 인자로 들어온 초기값을 malloc 후 초기화해준다

Destructor

다음으로 보이는 것은 아래에 보이는 ~이다.

std::__new_allocator<int>::~__new_allocator(&v23);

막상 뜯어보면 함수가 비어있는 것을 알 수 있는데, __new_allocator는 &v23에 해당하는 소멸자를 호출해주는 함수이지만, int의 소멸자가 정의되어 있지 않았기에 함수 정의가 비어있는 것이다.

at and push and pop

v35 = *(_DWORD *)std::vector<int>::at(v22, 1);
std::vector<int>::push_back(v22, &v24);
std::vector<int>::pop_back(v22);

위 세 함수는 vector의 기본 operator들이다. 여기서 v22는 vector의 주소이고 v24는 push하려는 대상이다.

at

__int64 __fastcall std::vector<int>::at(__int64 a1, __int64 a2)
{
  std::vector<int>::_M_range_check(a1, a2);
  return std::vector<int>::operator[](a1, a2);
}

c와는 다르게 매번 at이 호출될시 range check가 수반되며, 통과되었을시 operator[]를 통해서 값을 반환한다. operator[]는 구현을 보면 return 4 * a2 + *a1;와 같이 되어 있는 걸 봐서, template를 통해서 전해진 타입을 바탕으로 [] operator을 구현하는 것 같다.

push_back

__int64 __fastcall std::vector<int>::push_back(__int64 a1, __int64 a2)
{
  __int64 v2; // rax

  v2 = std::move<int &>(a2);
  return std::vector<int>::emplace_back<int>(a1, v2);
}

cpp에서 중요하고도 중요한 lvalue, rvalue를 여기서도 확인할 수 있다. move를 통해서 값을 emplace_back로 전달한다. 다만, <int&>를 move 하는 중이라, std::move<int &>를 뜯으면 단순히 입력을 반환하는 함수가 나온다.

emplace_back은 아래와 같이 구현되었다.

__int64 __fastcall std::vector<int>::emplace_back<int>(__int64 a1, __int64 a2)
{
  _DWORD *v2; // rbx
  __int64 v3; // rax
  __int64 v5; // [rsp+18h] [rbp-38h]
  void *v6; // [rsp+20h] [rbp-30h]
  __int64 v7; // [rsp+28h] [rbp-28h]

  if ( *(_QWORD *)(a1 + 8) == *(_QWORD *)(a1 + 16) )
  {
    v3 = std::forward<int>(a2);
    std::vector<int>::_M_realloc_append<int>(a1, v3);
  }
  else
  {
    v7 = std::forward<int>(a2);
    v6 = *(void **)(a1 + 8);
    v5 = std::forward<int>(v7);
    v2 = (_DWORD *)operator new(4u, v6);
    *v2 = *(_DWORD *)std::forward<int>(v5);
    *(_QWORD *)(a1 + 8) += 4LL;
  }
  return std::vector<int>::back(a1);
}

잠시 vector의 구조를 복기해 보자. vector를 가리키는 포인터를 a1이라 할 때 a1[0]은 vector의 memory주소, a[1]은 vector의 현재 마지막 주소, a[2]는 vector의 할당된 주소의 끝을 가리킨다. 따라서 emplace_back의 if문은 메모리를 모두 썼는지 확인하는 역할을 한다.

vector는 넉넉하게 메모리를 미리 할당받아서 매번 메모리 allocation이 발생하지 않도록 한다. 위 if문은 미리 할당 받은 메모리를 모두 사용했을 때, 일정 양만큼 할당을 받기 위한 코드이다.

만약 a[1]==a[2]라면 메모리를 할당받으면서 뒤에 a2를 삽입하고, 아닐 경우 copy 또는 move를 통해서 데이터를 a[1]위치에 삽입한다. 이후 a[1]+4를 통해 위치를 업데이트해준다.

pop_back

__int64 __fastcall std::vector<int>::pop_back(__int64 a1)
{
  *(_QWORD *)(a1 + 8) -= 4LL;
  return a1;
}

위처럼 a[1]의 값을 변경해서 pop 한다.

uaf leak에 쓰이려나

loops

for ( i = std::vector<int>::begin(v24); ; __gnu_cxx::__normal_iterator<int *,std::vector<int>>::operator++(&i, 0) )
{
    v27 = std::vector<int>::end(v24);
    if ( !(unsigned __int8)__gnu_cxx::operator<<int *,std::vector<int>>(&i, &v27) )
        break;
    v37 = *(_DWORD *)__gnu_cxx::__normal_iterator<int *,std::vector<int>>::operator*(&i);
}

forloop은 일반적인 loop과 range-based loop의 구현이 조금 달랐다. 구조적으로는 for과 while 정도의 차이라서 차이가 없다고 보는 것이 더 맞겠다. 그중 forloop으로 구현된 것을 살펴볼 것이다.

loop은 아래의 순서로 진행된다.

  1. i = std::vector<int>::begin(vec)
  2. i<end가 아니라면 break
  3. user defined works
  4. __gnu_cxx::__normal_iterator<int *,std::vector<int>>::operator++를 이용한 값 업데이트

c에서 자주보이던 i++가 internal 함수로 대체된다는 것만 기억하면 될 듯하다.

destructor

main 함수가 완전히 종료되기 이전, ~vector을 통해서 소멸자가 실행된다.

__int64 __fastcall std::vector<int>::~vector(_QWORD *a1)
{
  std::_Vector_base<int>::_M_get_Tp_allocator(a1);
  std::_Destroy<int *>(*a1, a1[1]);
  return std::_Vector_base<int>::~_Vector_base(a1);
}
  1. a1에 해당하는 allocator를 가져온다.
  2. a1부터 a1[1]까지의 원소들에 대해 소멸자를 호출한다.
  3. base class에 대한 소멸자를 호출한다.

Review

C++ 에서는 template를 활용해서 코드를 작성하다보니, c처럼 캐스팅를 바탕으로 메모리를 접근하지 않고 타입에 맞는 연산을 통해서 메모리 주소를 구한다는 것을 할 수 있다. 이에 따라 C++로 짜여진 프로그램을 분석할 때에는 자료형에 대한 빠른 파악과, unstripped code 상태에서 구조를 얼추 알고 있는 것이 큰 도움이 되는 것 같다. 또, 의미 없어보이는 코드조각들도 std::move<int &>와 같이 구조적으로 필요하지만, 실질적으로 사용되지 않는 경우가 잦기 때문에 call stack를 의미없이 쫓아가는 것은 지양하는 것이 좋을 것 같다.

APPENDIX: stripped version

__int64 __fastcall main(int a1, char **a2, char **a3)
{
  __int64 v3; // rax
  __int64 v4; // rdx
  __int64 v5; // rax
  __int64 v6; // rdx
  __int64 v7; // rax
  __int64 v8; // rdx
  __int64 v9; // rax
  __int64 v10; // rdx
  __int64 v11; // rax
  __int64 v12; // rdx
  __int64 v13; // rax
  __int64 v15; // [rsp+8h] [rbp-128h] BYREF
  __int64 v16; // [rsp+10h] [rbp-120h] BYREF
  __int64 v17; // [rsp+18h] [rbp-118h] BYREF
  __int64 v18; // [rsp+20h] [rbp-110h] BYREF
  __int64 i; // [rsp+28h] [rbp-108h] BYREF
  _BYTE v20[32]; // [rsp+30h] [rbp-100h] BYREF
  _DWORD v21[16]; // [rsp+50h] [rbp-E0h] BYREF
  _BYTE v22[35]; // [rsp+90h] [rbp-A0h] BYREF
  char v23; // [rsp+B3h] [rbp-7Dh] BYREF
  int v24; // [rsp+B4h] [rbp-7Ch] BYREF
  __int64 v25; // [rsp+B8h] [rbp-78h] BYREF
  char v26; // [rsp+C7h] [rbp-69h] BYREF
  int v27; // [rsp+C8h] [rbp-68h] BYREF
  int v28; // [rsp+CCh] [rbp-64h] BYREF
  char *v29; // [rsp+D0h] [rbp-60h]
  char *v30; // [rsp+D8h] [rbp-58h]
  int v31; // [rsp+E0h] [rbp-50h]
  int v32; // [rsp+E4h] [rbp-4Ch]
  _BYTE *v33; // [rsp+E8h] [rbp-48h]
  _BYTE *v34; // [rsp+F0h] [rbp-40h]
  int v35; // [rsp+FCh] [rbp-34h]

  v3 = std::operator<<<std::char_traits<char>>(&std::cout, "This program helps basic understanding of c++ program", a3);
  std::ostream::operator<<(v3, &std::endl<char,std::char_traits<char>>);
  v5 = std::operator<<<std::char_traits<char>>(&std::cout, "Below codes are initialization of vector", v4);
  std::ostream::operator<<(v5, &std::endl<char,std::char_traits<char>>);
  v30 = &v23;
  sub_1796(v22, &unk_41C0, 7, &v23);
  sub_1CBA(&v23);
  v7 = std::operator<<<std::char_traits<char>>(&std::cout, "push", v6);
  std::ostream::operator<<(v7, &std::endl<char,std::char_traits<char>>);
  v24 = 7;
  sub_187C(v22, &v24);
  sub_18AE(v22);
  v35 = *(_DWORD *)sub_18F4(v22, 1);
  for ( i = sub_192C(v22); ; sub_19B6(&i, 0) )
  {
    v25 = sub_1952(v22);
    if ( !(unsigned __int8)sub_197B(&i, &v25) )
      break;
    v35 = *(_DWORD *)sub_19F4(&i);
  }
  v34 = v22;
  v18 = sub_192C(v22);
  v17 = sub_1952(v34);
  while ( (unsigned __int8)sub_1A05(&v18, &v17) )
  {
    v31 = *(_DWORD *)sub_19F4(&v18);
    v35 = v31;
    sub_1A40(&v18);
  }
  v9 = std::operator<<<std::char_traits<char>>(&std::cout, "Below codes are initialization of plain C array", v8);
  std::ostream::operator<<(v9, &std::endl<char,std::char_traits<char>>);
  v21[8] = 0;
  v21[9] = 1;
  v21[10] = 2;
  v21[11] = 3;
  v21[12] = 4;
  v21[13] = 5;
  v21[14] = 6;
  v35 = v21[15];
  v11 = std::operator<<<std::char_traits<char>>(&std::cout, "Below codes are initialization of plain Cpp array", v10);
  std::ostream::operator<<(v11, &std::endl<char,std::char_traits<char>>);
  v21[0] = 0;
  v21[1] = 1;
  v21[2] = 2;
  v21[3] = 3;
  v21[4] = 4;
  v21[5] = 5;
  v21[6] = 6;
  v35 = *(_DWORD *)sub_1A60(v21, 0);
  v13 = std::operator<<<std::char_traits<char>>(&std::cout, "Below codes are initialization of plain Cpp list", v12);
  std::ostream::operator<<(v13, &std::endl<char,std::char_traits<char>>);
  v29 = &v26;
  sub_1A82(v20, &unk_41E0, 7, &v26);
  sub_1CBA(&v26);
  v27 = 7;
  sub_1B7C(v20, &v27);
  v28 = 8;
  sub_1BC4(v20, &v28);
  v33 = v20;
  v16 = sub_1C0C(v20);
  v15 = sub_1C34(v33);
  while ( (unsigned __int8)sub_1C59(&v16, &v15) )
  {
    v32 = *(_DWORD *)sub_1C9C(&v16);
    v35 = v32;
    sub_1C7C(&v16);
  }
  sub_1742(v20);
  sub_1826(v22);
  return 0;
}

보다시피, std 관련 함수들의 symbol이 제거되어 파악하기 어려워진다.

[Study]의 다른 글펼치기
[Rev] Cpp Vector analysis