STL容器逆向與實戰 - 網安 - 專業的網絡安全產業、社區、知識平臺

一、序言

在之前的CTF中常常出現了對STL容器的逆向，而在網上的資料中并沒有搜到詳細的STL容器逆向的經驗和文章，這里配合編譯器一起來看看常見的STL容器的內存模型，最后根據最近N1CTF比賽中cppmaster來進行實戰。

STL存在非常多種類的容器，但是多個容器之間的底層實現其實是類似的，例如set和map都采用的是rb_tree這個結構，因此我們從這種底層實現的數據結構來對STL容器分類，這里將要分析的容器分為分析四類：rb_tree,deque,hashtable,vector，順帶分析一下string的結構。

當然可能還存在許許多多的STL容器，但是大體的分析思路是類似的。這里采用LLVM輔助我們分析容器的內存結構。

二、Dump

對于一個Class而言，在LLVM IR種對應的為StructType，可以使用API訪問其下的子Type，因此可以隨便簡單寫個pass來dump出ir種的類的內存模型，從而輔助我們逆向分析各個容器的內存表示和實現。具體代碼如下：

#include "llvm/Pass.h"#include "llvm/IR/Function.h"#include "llvm/IR/CFG.h"#include "llvm/IR/Type.h"#include "llvm/ADT/SmallSet.h"#include "llvm/ADT/SmallVector.h"#include "llvm/IR/BasicBlock.h"#include "llvm/Support/raw_ostream.h"#include "llvm/IR/LegacyPassManager.h"#include "llvm/Transforms/Utils/Cloning.h"#include "llvm/Transforms/IPO/PassManagerBuilder.h"#include#includeusing namespace llvm;namespace{    struct DumpClass : public FunctionPass    {        static char ID;           DumpClass() : FunctionPass(ID) {}        std::string getTypeName(Type *type, DataLayout *data);        void dumpType(int depth, Type *type, int index, DataLayout *data);           bool runOnFunction(Function &F) override{             if(F.getName().compare("main"))                return false;            std::set types;            const DataLayout *data = &F.getParent()->getDataLayout();            for(Function::iterator B = F.begin(); B != F.end(); B++)            {                for(BasicBlock::iterator I = B->getFirstInsertionPt(); I != B->end(); I++)                {                    Instruction *instr = &*I;                    if(isa(*instr))                    {                        AllocaInst *a = (AllocaInst*)instr;                        Type *type = a->getAllocatedType();                        if(type->isStructTy())                        {                            StructType *s = (StructType*)type;                            if(s->isOpaque())                                continue;                            types.insert(s);                         }                    }                }            }            for(StructType *type:types)            {                errs()<<"start dumping type: " + type->getStructName() + "";                dumpType(0, type, 0, (DataLayout*)data);            }                return false;        }      };}std::string DumpClass::getTypeName(Type *type, DataLayout *data){    if(type->isIntegerTy())    {        IntegerType *i = (IntegerType*)type;        return "uint" + std::to_string(i->getBitWidth()) + "_t";    }    else if(type->isPointerTy())    {        PointerType *ptrType = (PointerType*)type;        return getTypeName(ptrType->getPointerElementType(), data) + "*";    }    else if(type->isArrayTy())    {        ArrayType *arrType = (ArrayType*)type;        return getTypeName(arrType->getArrayElementType(), data) + "[" + std::to_string(arrType->getArrayNumElements()) + "]";    }    else if(type->isFloatTy())    {        return "float";    }    else if(type->isStructTy())    {        StructType *s = (StructType*) type;        return s->getStructName();    }    else    {        return "unknown_" + std::to_string(data->getTypeAllocSizeInBits(type));    }}void DumpClass::dumpType(int depth, Type *type, int index, DataLayout *data){    std::string blank = "";    for(int i = 0; i < depth; i++)        blank += "\t";    if(type->isStructTy())    {        StructType *s = (StructType*)type;        errs() << blank + s->getStructName() + " {";        for(int i = 0; i < s->getStructNumElements(); i++)        {            Type *subType = s->getStructElementType(i);            dumpType(depth + 1, subType, i, data);        }        //        errs() << blank + "} field_" + std::to_string(index) + ";";    }    else    {        errs() << blank + getTypeName(type, data) + " field_" + std::to_string(index) + ";";    } }char DumpClass::ID=0;static RegisterPass X("dump", "DumpClass"); // Register for clangstatic RegisterStandardPasses Y(PassManagerBuilder::EP_EarlyAsPossible,  [](const PassManagerBuilder &Builder, legacy::PassManagerBase &PM) {    PM.add(new DumpClass());  });

三、deque

deque是queue，stack，deque等線性容器的底層實現，通過dump工具可以dump出具體的內存結構如下。不難發現在deque中，主要分為三個部分，第一個用于描述map的，其中包含map大小和map的指針，第二個則是指向deque中起始元素的Deque_iterator，第三個則是指向了deque中結束元素的Deque_iterator。

class.std::deque<string> {    class.std::_Deque_base {        struct.std::_Deque_base<std::__cxx11::basic_string<char>, std::allocator<std::__cxx11::basic_string<char> > >::_Deque_impl {            struct.std::_Deque_base<std::__cxx11::basic_string<char>, std::allocator<std::__cxx11::basic_string<char> > >::_Deque_impl_data {                class.std::__cxx11::basic_string** map;                uint64_t map_size;                struct.std::_Deque_iterator {                    class.std::__cxx11::basic_string* cur;                    class.std::__cxx11::basic_string* first;                    class.std::__cxx11::basic_string* last;                    class.std::__cxx11::basic_string** map;                } start;                struct.std::_Deque_iterator {                    class.std::__cxx11::basic_string* cur;                    class.std::__cxx11::basic_string* first;                    class.std::__cxx11::basic_string* last;                    class.std::__cxx11::basic_string** map;                } finish;            } field_0;        } field_0;    } field_0;} field_0;

這里需要注意的是：deque對元素的保存采取了分塊保存的機制。deque采用一塊連續的內存保存了一系列的指針。其中map即指向這一塊連續的內存，換句話說map是一個指針，指向一個指針數組。而這個指針數組中的指針指向的則是一篇連續的，用于實際保存數據的內存區域，我們稱為data array(每個元素的大小取決于deque中的模板類型)，具體的內存示意圖可以如下圖所示。

而iterator的結構需要關注的是cur，他將直接指向數據數組中具體的元素，還有就是iterator下的map指針，這個元素則代表當前iterator指向的元素所在區塊對應map中地址，last和first則指向data array的起始和結束。因此可以得知start和finish的map并不一定是相同的(即start迭代器指向元素不一定和finish迭代器指向元素處在同一個data array中)，所以iterator在進行迭代的時候是需要根據map跳躍到不同的data array中。

四、vector

vector作為常見又方便的stl容器，其實現并不復雜，比上述的deque要簡單得多。vector僅僅由三個指針構成：start,finish,end_of_storage。start用于指向數組的第一個元素，而finish指向結束的位置，即最后一個元素后面。而end_of_storage指向當前為vector分配的堆空間的結束地址。

class.std::vector<string> {    struct.std::_Vector_base {        struct.std::_Vector_base<std::__cxx11::basic_string<char>, std::allocator<std::__cxx11::basic_string<char> > >::_Vector_impl {            struct.std::_Vector_base<std::__cxx11::basic_string<char>, std::allocator<std::__cxx11::basic_string<char> > >::_Vector_impl_data {                class.std::__cxx11::basic_string* start;                class.std::__cxx11::basic_string* finish;                class.std::__cxx11::basic_string* end_of_storage;            } field_0;        } field_0;    } field_0;} field_0;

為什么需要有一個end_of_storage呢，vector是一個動態的容器，他會根據元素數目分配固定內存，但是當有新的元素加入時，如果分配的固定內存不足以存放新的元素的話，則會進行擴容。因此，這個指針則用于對vector需要擴容時使用(需要注意的是元素的大小取決于模板類型type的大小，因此存在(finish-start)%sizeof(type)==0)。具體的內存示意圖可以如下圖所示。

五、rb_tree

rb_tree即紅黑樹，具體的定義可以去網上翻閱資料，這里并不討論其具體的實現和算法，僅僅討論其數據結構在內存中的表示。rb_tree分為兩個部分，一個適用于比較的key_compare，另一個則是header。重點分析header，header中存在一個node，和node_count。node即這個紅黑樹的起始節點，而node_count則代表這顆紅黑樹擁有多少的節點。node中描述了當前節點的顏色，父親節點，左兒子和右兒子節點。

class.std::map<string,string> {    class.std::_Rb_tree.6 {        struct.std::_Rb_tree<std::__cxx11::basic_string<char>, std::pair<const std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> >, std::_Select1st<std::pair<const std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > >, std::less<std::__cxx11::basic_string<char> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > > >::_Rb_tree_impl {            struct.std::_Rb_tree_key_compare {                struct.std::less {                    uint8_t value;                } key_compare;            } compare;            struct.std::_Rb_tree_header {                struct.std::_Rb_tree_node_base {                    uint32_t color;                    struct.std::_Rb_tree_node_base* parent;                    struct.std::_Rb_tree_node_base* left;                    struct.std::_Rb_tree_node_base* right;                } node;                uint64_t node_count;            } field_1;        } field_0;    } field_0;} field_0;

這里需要注意的是，當紅黑樹中不存在節點時，header中node的parent是0，而left和right則指向node自身。當插入了結點之后，這個parent則會指向樹的根節點，而left和right則指向紅黑樹的最左邊的節點和最右邊的節點。

同時需要分清楚rb_tree變量本身和樹本身。rb_tree變量中的node是不攜帶具體數據元素的，而樹本身的節點在其node_base結構體結束后的內存區域則是數據元素。具體的內存示意圖如下圖所示。

map和set的實現皆是基于rb_tree，而唯一不同之處在于set直接在node中存儲數據，而map在node中存儲的是鍵值對，是一個pair，而pair在內存中的表示則是直接a后存放b。

六、hashtable

unordered_map和unordered_set的底層是由hashtable實現的。Prime_rehash_policy結構體適用于hashtable的rehash操作的不做分析，這里我們主要需要關注的是buckets，這個指針指向了一個_Hash_node_base*數組，如果指針為null則無效，這些指針數組中的指針指向的是一個鏈表，可以通過不斷的訪問next遍歷鏈表中的所有node。

bucket_count則表示buckets的大小，而element_count指的當前hashtable中所有的節點數目。默認的hashtable采用取模的方式找到對應的bucket，bucket_count一般為13。

class.std::unordered_map<int, string> {        class.std::_Hashtable {                struct.std::__detail::_Hash_node_base** buckets;                uint64_t bucket_count;                struct.std::__detail::_Hash_node_base {                        struct.std::__detail::_Hash_node_base* next;                } field_2;                uint64_t element_count;                struct.std::__detail::_Prime_rehash_policy {                        float max_load_factor;                        uint64_t next_resize;                } field_4;                struct.std::__detail::_Hash_node_base* field_5;        } field_0;} field_0;

因此需要遍歷一個hashtable只需要遍歷其bucket找到有效的list，并遍歷各個list就能找到所有的數據了，類似rb_tree，元素的數據存儲與鏈表結構_Hash_node_base的后面。具體的內存模型如下圖所示。

七、string

string的結構比較簡單。主要由一個指針ptr和字符串長度string_length構成。除此之外還會存在一個聯合體，當字符串的長度小于8時會直接存儲與這個緩沖區中，此時ptr指針將指向這個local_buf，大于這個local_buf將會在堆上另外分配內存，此時這個union轉而用于存儲分配堆的大小。

class.std::__cxx11::basic_string {    struct.std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_Alloc_hider {        uint8_t* ptr;    } dataplus;    uint64_t string_length;    union.anon {        uint64_t allocated_capacity;        uint8_t local_buf[8];    };} field_0;

這樣設計的目的是方便字符串大小變化的適應，便于實現字符串拼接等工作，且小字符串不用在堆上分配，對速度有少量提升。具體的內存示意圖如下圖所示，左邊的是長度小于8的string。

八、N1CTF2022 cppmaster

該題給與了一個ELF文件，并給出了hint.txt:Recursive stl containers ( > 3 ), Identify and traverse these containers

不難知道這個題目與STL容器密切相關，配合traverse不難猜測肯定是使用stl容器套容器的操作，先打開ida看看實現，找到main函數。

經過動調，可以定位到代碼輸入函數所在位置，在main中給他命名為input_check。而他上面的函數明顯初始化了一個deque的數據結構，第一行對應map，第二行對應map_size，接下來是兩個iterator，四個qword一組。

點開每個iterator的cur，也就是cur，可以看到其中存儲了兩個元素。

如果理解了上述的數據結構內存模型，很容易看出來其實是rb_tree，第一個qword是compare_key，第二個qword是color，第三個qword代表parent，第四個和第五個是left和right，第六個qword則代表node_count，因此其實就是deque>這種嵌套方式。

隨意點開rb_tree中的一個node，分析一下rb_tree對應的模板類型，可以看到他存儲的其實是std::pair，所以其實是deque>>，為什么我會知道是int呢，因為后文分析輸入流時輸入的都是數字，并通過數字從容器中訪問內部數據。

繼續查看一下hash_table的buckets。

隨意點開一個bucket，里面存儲的是個鏈表，鏈表節點數據中存儲的也是一個std::pair，因此這其實是一個unordered_map。

到這里我們對該變量有了大體的認識，大概率是不斷地stl容器嵌套，接下來繼續去分析輸入和這些容器之間的關系。input_check函數通過input_num輸入一個數字，并且返回該容器對應元素。這個明顯是deque的取元素操作。

然后通過step1跳轉到下一層，下一層和input_check邏輯其實是差不多的，也是輸入一個數字，然后獲取map中對應的元素。

然后通過step2跳轉到下一層，持續同樣的操作，只不過這一層是unordered_map罷了。

這樣的順序剛好和我們之前分析的數據類型嵌套的順序相符，所以我們需要根據這些函數來反推出這些數據結構的嵌套順序。不難發現unordered_map的代碼明顯存在一個取mod的操作，而map存在std::rebalanced的操作。因此可以寫出如下腳本來分析出容器的嵌套類型。

import ida_bytesimport ida_funcsimport ida_xrefimport idaapistep_funcs = {}funclist = Functions()rebalance_func = Nonefor f in funclist:    name = ida_funcs.get_func_name(f)    if 'step' in name:        step_funcs[name] = f    elif 'rebalance' in name:        rebalance_func = fassert rebalance_func != None step_type = {}for name, addr in step_funcs.items():    code = str(idaapi.decompile(addr))    if 'rebalance' in code:        step_type[name] = 'map'    elif '%' in code:        step_type[name] = 'hash_map'    else:        step_type[name] = 'deque' for i in range(28):    print('\'' + step_type['step' + str(i + 1)] + '\'' + ', ', end = '')

然后根據上述的出的容器嵌套順序和對應容器的內存模型dump出對應的數據結構。

import ida_bytesimport idaapi size_table = {    'map' : 48,    'deque' : 80,    'string' : 32,    'hash_map' : 16,} def dump_rbtree_node(addr):    return {        'color' : ida_bytes.get_qword(addr),        'parent' : ida_bytes.get_qword(addr + 8),        'left' : ida_bytes.get_qword(addr + 16),        'right' : ida_bytes.get_qword(addr + 24),    }  def dump_rbtree_map(addr):    key = ida_bytes.get_qword(addr)    node_addr = addr + 8    node_num = ida_bytes.get_qword(addr + 40)    result = {}    def visit(node):        if node == idaapi.BADADDR:            return        info = dump_rbtree_node(node)        assert info['color'] == 1 or info['color'] == 0        value_key = ida_bytes.get_qword(node + 32)        data_addr = node + 40        result[value_key] = data_addr        if info['left'] != 0:            visit(info['left'])        if info['right'] != 0:            visit(info['right'])    d = dump_rbtree_node(node_addr)    visit(d['parent'])    assert len(result.keys()) == node_num    return result def dump_deque_iterator(addr):    return {        'cur' : ida_bytes.get_qword(addr),        'first' : ida_bytes.get_qword(addr + 8),        'last' : ida_bytes.get_qword(addr + 16),        'map' : ida_bytes.get_qword(addr + 24),    } def dump_deque(addr, delta):    deque_map = ida_bytes.get_qword(addr)    map_size = ida_bytes.get_qword(addr + 8)    assert map_size == 8    start = dump_deque_iterator(addr + 16)    finish = dump_deque_iterator(addr + 16 + 32)    assert start['last'] == finish['last'] and start['first'] == finish['first'] and start['map'] == finish['map']    assert (finish['cur'] - start['cur']) % delta == 0    ptr = start['cur']    index = 0    result = {}    while ptr != finish['cur']:        result[index] = ptr        index += 1        ptr += delta    return result def dump_string(addr):    data = ida_bytes.get_qword(addr)    length = ida_bytes.get_qword(addr + 8)    return ida_bytes.get_bytes(data, length).decode() def dump_hashtable_map(addr):    addrs = set()    hash_table = ida_bytes.get_qword(addr)    table_num = ida_bytes.get_qword(addr + 8)    for i in range(table_num):        link_list = ida_bytes.get_qword(hash_table + 8 * i)        if link_list == 0:            continue        ptr = ida_bytes.get_qword(link_list)        while ptr != 0:            assert ptr != idaapi.BADADDR            addrs.add(ptr)            ptr = ida_bytes.get_qword(ptr)    result = {}    for a in addrs:        result[ida_bytes.get_qword(a + 8)] = a + 16    return result type_list = ['deque', 'map', 'hash_map', 'deque', 'map', 'map', 'hash_map', 'hash_map', 'map', 'map', 'hash_map', 'map', 'map', 'deque', 'deque', 'map', 'map', 'map', 'map', 'map', 'map', 'map', 'map', 'map', 'map', 'map', 'deque', 'deque', 'string']  def dump_dfs(depth, addr):    stl_type = type_list[depth]    tmp = {}    if stl_type == 'map':        tmp = dump_rbtree_map(addr)    elif stl_type == 'hash_map':        tmp = dump_hashtable_map(addr)    elif stl_type == 'deque':        next_type = type_list[depth + 1]        tmp = dump_deque(addr, size_table[next_type])    elif stl_type == 'string':        return dump_string(addr)    else:        assert False    node = {}    for k, v in tmp.items():        node[k] = dump_dfs(depth + 1, v)    return noderesult = dump_dfs(0, 0x7FFEA5D3A460)import jsonwith open('json_data.txt','w+') as f:    json.dump(result, f)#dump_rbtree_map(0x55F47B277658)

最后得到如下數據文件，是一個dict的嵌套，最后保存的是字符串。

最后main函數通過對比字符串，來判斷我們輸入的一系列數字是否能夠訪問到對應的字符串，從而判斷數字是否正確。

最后根據dump出的dict從而寫出dfs查找出對應的數字序列，從而獲得flag。

target = '8850a16d-e427-446e-b4df-5f45376e20e4'path = []def dfs(depth, node):    global path    if type(node) == dict:        for k, v in node.items():            path.append(k)            dfs(depth + 1, v)            path.pop()    else:        if node == target:            print(path)import jsonf = open('json_data.txt','r')data = json.load(f)f.close()dfs(0, data)