การสร้าง Storage Dependency Graph ของ SAILFISH

บทความที่แล้ว เราสรุปการทำงานคร่าวๆของ SAILFISH ไปแล้ว part นี้เรามาลองแกะ code เค้ากัน

โอเค มาเริ่มกัน

Storage Dependency Graph คืออะไร ?

คือกราฟที่จะบอกเราว่าแต่ละ function ใน smart contract มีการไป อ่าน/เขียน state variable ตัวไหนบ้าง (พูดอีกอย่างคือ การไป อ่านเขียน storage เพราะ state variable บันทึกค่าใน storage)

เช่น จาก function withdrawBalance

contract Reentrancy {
    mapping (address => uint) userBalance;
    mapping (address => uint) success;
    bool mutex;
    
    ...
     
     This function is guarded by mutex and hence even if there is a state change after the 
     external call the attacket can not weaponize that to re-enter the function
    */
    function withdrawBalance(uint amount) public{
        
        if (mutex == false)
        {
            mutex = true;
            if (userBalance[msg.sender] > amount)
            {
                msg.sender.call.value(amount)();
                userBalance[msg.sender] = userBalance[msg.sender] - amount;
            }
            mutex = false;
        }
    }    
}

เราจะรู้ได้ยังไงว่า withdrawBalance ไปยุ่งกับ state variable ตัวไหนบ้าง

โอเค มาดู code ต้นฉบับกันก่อน โดยวิธีที่ SAILFISH ทำคือ

1. ใช้ Slither สร้าง call graph

# Initialize Slither
slither_obj = Slither(contract_path, solc=solc_path)
target_contracts = get_child_contracts(slither_obj)

# Generate callgraph
log.info('Callgraph generation started!')
callgraph = CallGraph(slither_obj, graph_dir, dump_graph, log)
log.info('Callgraph generation finished!')

เอาละ ก่อนอื่น call graph คืออะไร

call graph คือ graph ที่แสดงว่า แต่ละ function มีการเรียกหากันรึเปล่า

เช่น callgraph ของ contract นี้คือ

ซึ่งจากภาพ function ต่างๆใน contract ไม่ได้มีการเรียกใช้กันเองเลย

โอเค พอเรารู้ว่าแต่ละ function มีการเรียกใช้กันรึเปล่า ต่อมา SAILFISH ก็ได้ใช้ Slither ในการสร้าง

2. ใช้ Slither สร้าง ICFG (Inter procedural Control Flow Graph)

# Build interprocedural cfg for all public functions
log.info('Interprocedural CFG generation started!')
generated_icfg, icfg_objects = generate_icfg(slither_obj, callgraph, graph_dir, dump_graph, log)
log.info('Interprocedural CFG generation finished!')

โอเค ก่อนที่จะอธิบายว่า ICFG คืออะไร

เราต้องมาดูว่า CFG (Control Flow Graph) คืออะไรก่อน

CFG คือกราฟที่แสดง flow การทำงานของ function

เช่นจากรูป คือ CFG ของ function withdrawBalance

โอเค ลองมาเทียบรูปกับ code กัน

จาก code ถ้า mutex == false จะเข้าไปทำงานใน IF ถ้าไม่ใช่จะจบโปรแกรม

function withdrawBalance(uint amount) public{
    
    if (mutex == false)
    {
        mutex = true;
        if (userBalance[msg.sender] > amount)
        {
            msg.sender.call.value(amount)();
            userBalance[msg.sender] = userBalance[msg.sender] - amount;
        }
        mutex = false;
    }
}    

แล้วจากรูปละ

จากรูปเราจะเห็นว่า verticle แรกของ graph จะเป็นแค่ entry point

ต่อมาใน block 8 เราจะพบว่ามีการเช็คว่าค่า mutex == False รึเปล่า

ถ้าใช่จะไปทำงานใน block 9 ต่อ (สังเกตุได้จากที่ call context = True)

โดยสรุปแล้ว CFG คือ graph ที่แสดง flow การทำงานของโปรแกรม

ในการหาว่าโปรแกรมรันอะไรบ้าง

เราก็ต้องดูว่าทุกคำสั่งถูกรันหมดมั้ย

หรือมีเงื่อนไข IF ELSE ในการรันคำสั่งด้วย

ดังนั้นเราจึงต้องวาด flow การรันของคำสั่งออกมาเป็นกราฟต้นไม้นั่นเอง

โดยแต่ละ verticle ในกราฟ จะเป็นชุดคำสั่งที่ถูกรันต่อกัน ไม่มีการ JUMP หรือ เงื่อนไขในการรันคำสั่งใดๆ

เราเรียกแต่ละ verticle ว่า basic block

โอเค CFG ก็จะประมาณนี้

แล้ว ICFG คืออะไร

ICFG = CFG + Call graph

คือตัว CFG เนี่ย จะแสดง flow การทำงานของฟังก์ชันหนึ่งๆ

และ Call graph จะแสดงว่าแต่ละ function มีการเรียกใช้กันรึเปล่า

ดังนั้น ถ้าเราเอาทั้ง 2 กราฟมาผสมกัน

เราจะได้กราฟที่แสดงทั้งการเรียกใช้กันของแต่ละ function และแสดงลึกลงไปถึงว่าแต่ละ function มี flow การทำงานยังไง

โดย withdrawBalance เนี่ยไม่มีการเรียก function อื่น / ถูก function อื่น เรียก

ดังนั้น CFG = ICFG ในเคส withdrawBalance นั่นเอง

3. สร้าง SICFG (Simplified ICFG )จาก ICFG

โอเค ดูเหมือน part นี้จะเป็น part ที่ SAILFISH เขียน logic เองทั้งหมดแล้ว

โดย SAILFISH จะทำการ simplified ให้ ICFG เหลือแค่คำสั่งที่มีการแก้ state variables

def setup(self):
    # This generates a simplified icfg containting basic blocks which can change the state of the
    # contract, for now we just consider 1, 4, 6

    self._sicfg = self.build_simplified_icfg()

ซึ่งเค้าได้สรุป pattern คำสั่งที่เกี่ยวกับการแก้ state variables ไว้ 6 pattern

แต่เค้าตี scope งานตัวเอง ไว้แค่การ simplified ด้วย 3 pattern (1 4 6)

'''
Functions can be declared view in which case they promise not to modify the state.
The following statements are considered modifying the state:
1. Writing to state variables. (We consider)
2. Emitting events. (We consider)
2. Creating other contracts.
3. Using selfdestruct.
4. Sending Ether via calls. (We consider)
5. Calling any function not marked view or pure.
6. Using low-level calls. (We consider)
7. Using inline assembly that contains certain opcodes.

'''

โดย logic ในการ simplified จะมีหลายขั้นตอน (เช่นการ detect phi node ซึ่งเป็นเรื่องเกี่ยวกับ compiler design/intermediate representation ละ)

# If the instr block list is empty and it has two predecessors 
# then assume it is a phi node and create a separate instr block for that
if len(predecessors) > 1 and len(instr_block_list) == 0:
    instr_block = InstrBlock("Phi Node")
    instr_block._instr_to_node = basic_block
    instr_block_list.append(instr_block)

แต่ step หลักๆคือการดูว่าคำสั่งนั้นๆ เป็นคำสั่งเกี่ยวกับ state variable มั้ย หรือแค่ใช้ memory (ตัวแปร local อย่างเดียว)

if type(var_used).__name__ == 'StateVariableSolc':
    var_used = SDG.map_svars_to_sobj[var_used]
    if instr not in state_vars.keys():
        state_vars[instr] = []
    
    state_vars[instr].append(var_used)

if type(var_used).__name__ == 'ReferenceVariable':
    if var_used not in CFG.member_ir_var_left and type(var_used.points_to_origin).__name__ != 'LocalVariableSolc':
        origin_var = self.get_origin_state_var(var_used)

โดยเมื่อดูจากรูป SICFG ด้านล่าง จะเห็นว่า เหมือนเค้าหั่น basic block ออก เป็นย่อยๆ เมื่อมีการเข้าถึง state variable ตัวที่ต่างกันด้วย (แยกการเข้าถึง mutex และ user balance ออกเป็น block 8 และ 9)

โอเค เมื่อเค้า format SICFG ให้เหลือเท่าที่มีการยุ่งกับ storage ได้แล้ว ก็มาถึงขั้นสุดท้าย

4. สร้าง SDG จาก SICFG

จากคำอธิบาย code เค้าบอกว่า จาก SICFG เค้าจะลากเส้นที่ระบุถึง data flow ของการเรียกใช้ storage variable เพื่อทำให้ SICFG กลายเป็น CFG

def setup(self):
    # This generates a simplified icfg containting basic blocks which can change the state of the
    # contract, for now we just consider 1, 4, 6

    self._sicfg = self.build_simplified_icfg()

    # Get the root and the leaf nodes of the sicfg
    self._root_nodes = self.get_root_nodes(self._sicfg)
    self._leaf_nodes = self.get_leaf_nodes(self._sicfg)

    # Given the sicfg we build the storage dependency graph by adding the data flow edges
    # from the storage variables

    self._sdg = self.build_sdg(self._contract, self._function, self._sicfg)
    SDG.sdg_generated[self._function] = self._sdg

พอเรามาดูรูป SDG เราจะพบว่า เค้ามีการลากเส้นประเพื่อดูว่าเวลาเราแก้ state variable ไปแล้ว มีการเข้าถึง state variable นั้น ที่ block ไหนบน instruction ก่อนหน้า

โอเค ตอนนี้เราจะได้ SDG มาละ

เข้าใจว่า step ต่อไปจะเป็นการหา external call ที่ตรงตาม pattern reentrancy (simplified as state inconsistency pattern) โดยใช้ static analysis ละนะ

Referrences

SAILFISH: Vetting Smart Contract State-Inconsistency Bugs in Seconds

GitHub - ucsb-seclab/sailfish: Data and code for the IEEE S&P'22 paper SAILFISH: Vetting Smart…

https://www2.cs.arizona.edu/~collberg/Teaching/453/2009/Handouts/Handout-15.pdf

ir

Practical differences between control flow graph and call (flow?) graph?