[Rev] Cpp Vector analysis

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은 아래의 순서로 진행된다.

i = std::vector<int>::begin(vec)
i<end가 아니라면 break
user defined works
__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);
}

a1에 해당하는 allocator를 가져온다.
a1부터 a1[1]까지의 원소들에 대해 소멸자를 호출한다.
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이 제거되어 파악하기 어려워진다.