FuzzILLI之FuzzIL

FuzzIL粗略分析

FuzzIL

FuzzIL是FUZZILLI使用的中间语言，FuzzIL由Lifter转换为语法正确的js代码

首先看看HowFuzzilliWorks里的一个FuzzIL的例子：

v0 <- BeginPlainFunctionDefinition -> v1, v2, v3
    v4 <- BinaryOperation v1 '+' v2
    StoreProperty v3, 'foo', v4
EndPlainFunctionDefinition
v5 <- LoadString "Hello World"
v6 <- CreateObject ['bar': v5]
v7 <- LoadFloat 13.37
v8 <- CallFunction v0, [v7, v7, v6]

在经过Lifter的转换后：

function v0(v1, v2, v3) {
    const v4 = v1 + v2;
    v3.foo = v4;
}
const v5 = "Hello World";
const v6 = {bar: v5};
const v7 = 13.37;
const v8 = v0(v7, v7, v6);

在文档里还说明了FuzzIL的几个重要属性：

• FuzzIL里的Program是由一系列instructions组成的
• 任何FuzzIL的Program都能被lift为语法正确的js代码
• FuzzIL的一条instruction由一个operation和输入输出variable组成，可能还带有一个或多个参数（如上面示例中由单引号括起来的）
• 任何的variable都是定义了之后才使用，并且变量名后的标号是连续的
• 控制流通过“Block”来描述，它至少有一个Begin和End的operation，但是也可以有intermediate operations，比如BeginIf, BeginElse, EndIf
• Block instructions可以有内部输出（在示例中’->’后面的那些），这些输出只在新打开的作用域中可见（如函数的参数）
• instructions 的输入总是variable，没有即时值
• instruction 的每一个输出都是一个新的variable，现有的variable只能通过专门的operation来重新分配，如Reassign指令

这几个属性中提到了Program，instruction，operation，variable，Block，这些都会在后面解释

FuzzIL的主要代码实现都在Sources\Fuzzilli\FuzzIL目录下：

Mode                 LastWriteTime         Length Name
----                 -------------         ------ ----
-a----          2022/5/6     14:23          29624 AbstractInterpreter.swift
-a----          2022/5/6     14:23           5812 Analyzer.swift
-a----          2022/5/6     14:23           9788 Blocks.swift
-a----          2022/5/6     14:23           3871 ClassUtils.swift
-a----          2022/5/6     14:23          11170 Code.swift
-a----          2022/5/6     14:23           1639 Context.swift
-a----          2022/5/6     14:23          38128 Instruction.swift
-a----          2022/5/6     14:23          35774 Operations.swift
-a----          2022/5/6     14:23           6052 Program.swift
-a----          2022/5/6     14:23           2215 ProgramComments.swift
-a----          2022/5/6     14:23           6039 ProgramTypes.swift
-a----          2022/5/6     14:23           6670 Semantics.swift
-a----          2022/5/6     14:23            988 TypeCollectionStatus.swift
-a----          2022/5/6     14:23           1246 TypeInfo.swift
-a----          2022/5/6     14:23          43682 TypeSystem.swift
-a----          2022/5/6     14:23           1587 Variable.swift

Context.swift

该文件定义了operation需要的context：

/// Current context in the program
public struct Context: OptionSet {
    public let rawValue: Int
    
    public init(rawValue: Int) {
        self.rawValue = rawValue
    }
    
    // Default script context
    public static let script            = Context(rawValue: 1 << 0)
    // Inside a function definition
    public static let function          = Context(rawValue: 1 << 1)
    // Inside a generator function definition
    public static let generatorFunction = Context(rawValue: 1 << 2)
    // Inside an async function definition
    public static let asyncFunction     = Context(rawValue: 1 << 3)
    // Inside a loop
    public static let loop              = Context(rawValue: 1 << 4)
    // Inside a with statement
    public static let with              = Context(rawValue: 1 << 5)
    // Inside a class definition
    public static let classDefinition   = Context(rawValue: 1 << 6)
    // Inside a switch block
    public static let switchCase        = Context(rawValue: 1 << 7)
    
    public static let empty             = Context([])
}

通俗易懂

Operation.swift

注释里说明了operation可以被不同的program共享

/// Operations can be shared between different programs since they do not contain any
/// program specific data.
public class Operation {
    /// The attributes of this operation.
    let attributes: Attributes
    
    /// The context in which the operation can exist
    let requiredContext: Context

    /// The context that this operations opens
    let contextOpened: Context

    /// The number of input variables to this operation.
    private let numInputs_: UInt16
    var numInputs: Int {
        return Int(numInputs_)
    }
    
    /// The number of newly created variables in the current scope.
    private let numOutputs_: UInt16
    var numOutputs: Int {
        return Int(numOutputs_)
    }
    
    /// The number of newly created variables in the inner scope if one is created.
    private let numInnerOutputs_: UInt16
    var numInnerOutputs: Int {
        return Int(numInnerOutputs_)
    }

    // ... //
    /// Possible attributes of an operation.
    struct Attributes: OptionSet {
        let rawValue: UInt16
        
        // The operation is pure, i.e. returns the same output given
        // the same inputs (in practice, for simplicity we only mark
        // operations without inputs as pure) and doesn't have any
        // side-effects. As such, two identical pure operations can
        // always be replaced with just one.
        static let isPure             = Attributes(rawValue: 1 << 0)
        // The operation has parameters that can for example be mutated.
        static let isParametric       = Attributes(rawValue: 1 << 1)
        // The operation performs a subroutine call.
        static let isCall             = Attributes(rawValue: 1 << 2)
        // The operation is the start of a block.
        static let isBlockBegin       = Attributes(rawValue: 1 << 3)
        // The operation is the end of a block.
        static let isBlockEnd         = Attributes(rawValue: 1 << 4)
        // The operation is the start of a loop (and thus of a block).
        static let isLoopBegin        = Attributes(rawValue: 1 << 5)
        // The operation is the end of a loop (and thus of a block).
        static let isLoopEnd          = Attributes(rawValue: 1 << 6)
        // The operation is used for internal purposes and should not
        // be visible to the user (e.g. appear in emitted samples).
        static let isInternal         = Attributes(rawValue: 1 << 7)
        // The operation behaves like an (unconditional) jump and
        // so any following code will not be executed.
        static let isJump             = Attributes(rawValue: 1 << 8)
        // The operation can take a variable number of inputs. Existing
        // inputs can be removed and new ones added.
        static let isVarargs          = Attributes(rawValue: 1 << 9)
        // The operation propagates the surrounding context
        static let propagatesSurroundingContext = Attributes(rawValue: 1 << 10)
    }
}

numInputs_和numOutputs_ 表明该operation所需的variable数量，如例子中的StoreProperty v3, 'foo', v4，它没有output，但是需要两个input的variable，还要带有一个属性名字；这也对应了它的定义：

class StoreProperty: Operation {
    let propertyName: String

    init(propertyName: String) {
        self.propertyName = propertyName
        super.init(numInputs: 2, numOutputs: 0, attributes: [.isParametric])
    }
}

attributes也是一个比较重要的成员，它表明了该operation的一些特性，后续lift和变异也会依赖这些特性

Variable.swift

variable的实现很简单：

/// A variable in the FuzzIL language.
///
/// Variables names (numbers) are local to a program. Different programs
/// will have the same variable names referring to different things.
public struct Variable: Hashable, CustomStringConvertible {
    // We assume that programs will always have less than 64k variables
    private let num: UInt16

    public init(number: Int) {
        self.num = UInt16(number)
    }

    public var number: Int {
        return Int(num)
    }

    public var identifier: String {
        return "v\(number)"
    }

    public var description: String {
        return identifier
    }

    public static func ==(lhs: Variable, rhs: Variable) -> Bool {
        return lhs.number == rhs.number
    }

    public static func isValidVariableNumber(_ number: Int) -> Bool {
        return UInt16(exactly: number) != nil
    }
}

extension Variable: Comparable {
    public static func <(lhs: Variable, rhs: Variable) -> Bool {
        return lhs.number < rhs.number
    }
}

内部会有一个num表示他是第几个变量，其名字就是v+’num’，如例子中的v1，v2；要注意的是不同的Program是可以用相同的变量名的

Instruction.swift

该文件定义了Instruction类：

/// The building blocks of FuzzIL code.
///
/// An instruction is an operation together with in- and output variables.
public struct Instruction {
    /// The operation performed by this instruction.
    public let op: Operation

    /// The input and output variables of this instruction.
    ///
    /// Format:
    ///      First numInputs Variables: inputs
    ///      Next numOutputs Variables: outputs visible in the outer scope
    ///      Next numInnerOutputs Variables: outputs only visible in the inner scope created by this instruction
    ///      Final value, if present, the index of this instruction in the code object it is part of.
    private let inouts_: [Variable]


   // ... //

    /// The index of this instruction in the Code it belongs to.
    /// A value of -1 indicates that this instruction does not belong to any code.
    public var index: Int {
        // We store the index in the internal inouts array for memory efficiency reasons.
        // In practice, this does not limit the size of programs/code since that's already
        // limited by the fact that variables are UInt16 internally.
        let indexVar = numInouts == inouts_.count ? nil : inouts_.last
        return Int(indexVar?.number ?? -1)
    }
	/// The number of input variables of this instruction.
    public var numInputs: Int {
        return op.numInputs
    }

    /// The number of output variables of this instruction.
    public var numOutputs: Int {
        return op.numOutputs
    }

    ///
    /// Flag accessors.
    ///

    /// A pure instructions returns the same value given the same inputs and has no side effects.
    public var isPure: Bool {
        return op.attributes.contains(.isPure)
    }

    /// Is this instruction parametric, i.e. can/should this operation be mutated by the OperationMutator?
    /// The rough rule of thumbs is that every Operation class that has members other than those already in the Operation class are parametric.
    /// For example integer values (LoadInteger), string values (LoadProperty and CallMethod), or Arrays (CallFunctionWithSpread).
    public var isParametric: Bool {
        return op.attributes.contains(.isParametric)
    }
	// ... //
}

如类的开头注释里所说，instruction由operation和一些in out的variable组成，比较重要的成员就是inouts_，该成员保存了in和out的variable还有一个index，该index是和Code相关的，用来表明该instruction在所属code（code就是由一连串的instruction组成的）中的位置；

在一堆in和out的getter定义后就是该instruction的flag，该flag对operation的attribute进行了一些简单的归类

该文件后面还有一个对Protobuf的支持，这不是我们分析的重点（看不动了）就跳过了

Code.swift

/// Code: a sequence of instructions. Forms the basis of Programs.
public struct Code: Collection {
    public typealias Element = Instruction

    /// Code is just a linear sequence of instructions
    private var instructions = [Instruction]()
    
    // ... //
}

code是由一连串的instruction组成的，在它内部最重要的一个函数就是check函数，check函数用来静态检查instruction是不是合法的：

/// Checks if this code is statically valid, i.e. can be used as a Program.
    public func check() throws {
        var definedVariables = VariableMap<Int>()
        var scopeCounter = 0
        var visibleScopes = [scopeCounter]
        var contextAnalyzer = ContextAnalyzer()
        var blockHeads = [Operation]()
        var defaultSwitchCaseStack: [Bool] = []
        var classDefinitions = ClassDefinitionStack()

        // ... //
    }

首先是开头的一连串变量定义，接着：

func defineVariable(_ v: Variable, in scope: Int) throws {
            guard !definedVariables.contains(v) else {
                throw FuzzilliError.codeVerificationError("variable \(v) was already defined")
            }
            if v.number != 0 {
                let prev = Variable(number: v.number - 1)
                guard definedVariables.contains(prev) else {
                    throw FuzzilliError.codeVerificationError("variable definitions are not contiguous: \(v) is defined before \(prev)")
                }
            }
            definedVariables[v] = scope
        }

check函数在内部声明了一个defineVariable函数用于定义variable，从error的提示来看，variable不允许重复定义且他们的id（v.number）一定要是连续的，也就是v1后面必须是v2，最后再把定义的variable和其所在的scope一起存入definedVariables这个map中

然后开始一个大循环，对该code所有的instruction进行检查：

for (idx, instr) in instructions.enumerated() {
            guard idx == instr.index else {
                throw FuzzilliError.codeVerificationError("instruction \(idx) has wrong index \(String(describing: instr.index))")
            }

            // Ensure all input variables are valid and have been defined
            for input in instr.inputs {
                guard let definingScope = definedVariables[input] else {
                    throw FuzzilliError.codeVerificationError("variable \(input) was never defined")
                }
                guard visibleScopes.contains(definingScope) else {
                    throw FuzzilliError.codeVerificationError("variable \(input) is not visible anymore")
                }
            }

            // Ensure that the instruction exists in the right context
            contextAnalyzer.analyze(instr)
            guard instr.op.requiredContext.isSubset(of: contextAnalyzer.context) else {
                throw FuzzilliError.codeVerificationError("operation \(instr.op.name) inside an invalid context")
            }
 			// .... //   
}

这是循环开头一些简单的check，比如instruction的index是否匹配，该指令input的variable是否已经都定义了，是否在scope中可见，在分析一下该指令的context是否正确

最后是block相关的检查：

// Block and scope management (1)
         if instr.isBlockEnd {
             guard let blockBegin = blockHeads.popLast() else {
                 throw FuzzilliError.codeVerificationError("block was never started")
             }
             guard instr.op.isMatchingEnd(for: blockBegin) else {
                 throw FuzzilliError.codeVerificationError("block end does not match block start")
             }
             visibleScopes.removeLast()

             // Switch Case semantic verification
             if instr.op is EndSwitch {
                 defaultSwitchCaseStack.removeLast()
             }

             // Class semantic verification
             if instr.op is EndClassDefinition {
                 guard !classDefinitions.current.hasPendingMethods else {
                     let pendingMethods = classDefinitions.current.pendingMethods().map({ $0.name })
                     throw FuzzilliError.codeVerificationError("missing method definitions for methods \(pendingMethods) in class \(classDefinitions.current.name)")
                 }
                 classDefinitions.pop()
             }
         }

         // Ensure output variables don't exist yet
         for output in instr.outputs {
             // Nop outputs aren't visible and so should not be used by other instruction
             let scope = instr.op is Nop ? -1 : visibleScopes.last!
             try defineVariable(output, in: scope)
         }

         // Block and scope management (2)
         if instr.isBlockBegin {
             scopeCounter += 1
             visibleScopes.append(scopeCounter)
             blockHeads.append(instr.op)

             // Switch Case semantic verification
             if let op = instr.op as? BeginSwitch, op.isDefaultCase {
                 defaultSwitchCaseStack.append(true)
             } else {
                 defaultSwitchCaseStack.append(false)
             }

             // Class semantic verification
             if let op = instr.op as? BeginClassDefinition {
                 classDefinitions.push(ClassDefinition(from: op, name: instr.output.identifier))
             } else if instr.op is BeginMethodDefinition {
                 guard classDefinitions.current.hasPendingMethods else {
                     throw FuzzilliError.codeVerificationError("too many method definitions for class \(classDefinitions.current.name)")
                 }
                 let _ = classDefinitions.current.nextMethod()
             }
         }

         // Ensure that we have at most one default case in a switch block
         if let op = instr.op as? BeginSwitchCase, op.isDefaultCase {
             let stackTop = defaultSwitchCaseStack.removeLast()

             // Check if the current block already has a default case
             guard !stackTop else {
                 throw FuzzilliError.codeVerificationError("more than one default switch case defined")
             }

             defaultSwitchCaseStack.append(true)
         }

         // Ensure inner output variables don't exist yet
         for output in instr.innerOutputs {
             try defineVariable(output, in: visibleScopes.last!)
         }

isBlockBegin和isBlockEnd对着看，isBlockBegin会将scopeCounter加1，visibleScopes变量在将scopeCounter添加进去，表示接下来的变量都属于新的scope，而isBlockEnd将最后一个scope移除；在isBlockBegin和isBlockEnd的中间是确保instruction的output变量的正确；isBlockBegin和isBlockEnd还涉及switch和classDefinition指令，他们检查的相关代码一部分在ClassUtils.swift，一部分在operation.swift文件里，俺理解的不是很透彻；

Program.swift

/// Immutable unit of code that can, amongst others, be lifted, executed, scored, (de)serialized, and serve as basis for mutations.
///
/// A Program's code is guaranteed to have a number of static properties, as checked by code.isStaticallyValid():
/// * All input variables must have previously been defined
/// * Variables have increasing numbers starting at zero and there are no holes
/// * Variables are only used while they are visible (the block they were defined in is still active)
/// * Blocks are balanced and the opening and closing operations match (e.g. BeginIf is closed by EndIf)
/// * An instruction always produces a new output variable
///
public final class Program {
    /// The immutable code of this program.
    public let code: Code
    
    /// The parent program that was used to construct this program.
    /// This is mostly only used when inspection mode is enabled to reconstruct
    /// the "history" of a program.
    public private(set) var parent: Program? = nil
    
    /// Comments attached to this program
    public var comments = ProgramComments()

    /// Current type information combined from available sources
    public var types = ProgramTypes()

    /// Result of runtime type collection execution, by default there was none.
    public var typeCollectionStatus = TypeCollectionStatus.notAttempted
    
    /// Each program has a unique ID to identify it even accross different fuzzer instances.
    public private(set) lazy var id = UUID()
    
    // ... //
}

Program类主要还是由code，comments和types三个组成，在其开头的注释中也说明了code该有的属性：

• 所有input的variable都必须是定义过的
• variable的number必须是从零开始，并且是依次递增的
• 只有可见的variable才能被使用，可见代表着vraiable所在的block还没有被销毁
• block是平衡的，也就是说那些带isBlockxxx属性的instruction必须配对（如BeginIf和EndIf）
• 一条instruction总是产生一个新的output的variable（这个不知道该怎么理解，因为从operation里的定义来看，有些operation是没有output的）

文件的后面还定义了对protobuf的支持（看不动了）

综合一下：

Program<--- ProgramComments
       <--- ProgramTypes
       <--- Code <--- Instruction <--- Operation
                 <--- Instruction <--- Variables
                 <--- Instruction
                 <--- ...

大概是这么个情况

接下来看一下ProgramComments和ProgramTypes

ProgramComments

相关实现在ProgramComments.swift里，代码不多，看着感觉像是拿来做记录用的

ProgramTypes

相关实现在ProgramTypes.swift里：

public struct ProgramTypes: Equatable, Sequence {
    private var types = VariableMap<[TypeInfo]>()

    public init () {}

    public init (from types: VariableMap<[TypeInfo]>) {
        self.types = types
    }

    // ... //
}

先看看这个TypeInfo：

// Sources\Fuzzilli\FuzzIL\TypeInfo.swift
public enum TypeQuality: UInt8 {
    case inferred
    case runtime
}

// Store known types for program variables at specific instructions
public struct TypeInfo: Equatable {
    private let _index: UInt16
    public let type: Type
    public let quality: TypeQuality
    public var index: Int {
        return Int(_index)
    }

    public init(index: Int, type: Type, quality: TypeQuality) {
        self._index = UInt16(index)
        self.type = type
        self.quality = quality
    }

    public static func == (lhs: TypeInfo, rhs: TypeInfo) -> Bool {
        return lhs._index == rhs._index && lhs.type == rhs.type && lhs.quality == rhs.quality
    }
}

这里面有个Type，其实现是在Sources\Fuzzilli\FuzzIL\TypeSystem.swift里，是需要着重分析的对象

Type

TypeSystem.swift文件开头有一长串的注释来解释这个TypeSystem，总的来说就是为了能够更好的生成语义正确的js代码

Type定义了BaseType和Type之间的一些操作：Unioning（|）、Intersecting （&）、Merging （+）；

首先来看看BaseType：

struct BaseType: OptionSet, Hashable {
    let rawValue: UInt32
    
    // Base types
    static let nothing     = BaseType([])
    
    // The compiler has these values hardcoded, in ProgramBuilder.ml.
    // If these values are changed, make sure to update them there as well.
    static let undefined   = BaseType(rawValue: 1 << 0)
    static let integer     = BaseType(rawValue: 1 << 1)
    static let float       = BaseType(rawValue: 1 << 2)
    static let string      = BaseType(rawValue: 1 << 3)
    static let boolean     = BaseType(rawValue: 1 << 4)
    static let object      = BaseType(rawValue: 1 << 5)
    static let function    = BaseType(rawValue: 1 << 6)
    static let constructor = BaseType(rawValue: 1 << 7)
    static let unknown     = BaseType(rawValue: 1 << 8)
    static let bigint      = BaseType(rawValue: 1 << 9)
    static let regexp      = BaseType(rawValue: 1 << 10)
    static let iterable    = BaseType(rawValue: 1 << 11)
    
    /// The union of all types.
    static let anything    = BaseType([.undefined, .integer, .float, .string, .boolean, .object, .unknown, .function, .constructor, .bigint, .regexp, .iterable])
    
    static let allBaseTypes: [BaseType] = [.undefined, .integer, .float, .string, .boolean, .object, .unknown, .function, .constructor, .bigint, .regexp, .iterable]
}

其中定义了两个特殊的basetype，一个是nothing，一个是anything

Type在实现上定义了两个bitsets，一个是definiteType，一个是possibleType，从代码的示例和注释来看，definiteType像是交集，possibleType像是并集：

/// Internally, types are implemented as bitsets, with each base type corresponding to one bit.
/// Types are then implemented as two bitsets: the definite type, indicating what it definitely
/// is, and the possible type, indicating what types it could potentially be.
/// A union type is one where the possible type is larger than the definite one.
///
/// Examples:
///    .integer                      => definiteType = .integer,          possibleType = .integer
///    .integer | .float             => definiteType = .nothing (0),      possibleType = .integer | .float
///    .string + .object             => definiteType = .string | .object, possibleType = .string | .object
///    .string | (.string + .object) => definiteType = .string,           possibleType = .string | .object
///
/// See also Tests/FuzzilliTests/TypeSystemTest.swift for examples of the various properties and features of this type system.
///

‘|’ 调用的是union函数， ‘+’ 调用的是merging函数 ，还有个‘&’ 调用的是intersection函数，这里就不贴了

Type还有一个ext的成员，其类型为TypeExtension：

class TypeExtension: Hashable {
    // Properties and methods. Will only be populated if MayBe(.object()) is true.
    let properties: Set<String>
    let methods: Set<String>
    
    // The group name. Basically each group is its own sub type of the object type.
    // (For now), there is no subtyping for group: if two objects have a different
    // group then there is no subsumption relationship between them.
    let group: String?
    
    // The function signature. Will only be != nil if isFunction or isConstructor is true.
    let signature: FunctionSignature?
    
    init?(group: String? = nil, properties: Set<String>, methods: Set<String>, signature: FunctionSignature?) {
        if group == nil && properties.isEmpty && methods.isEmpty && signature == nil {
            return nil
        }
        
        self.properties = properties
        self.methods = methods
        self.group = group
        self.signature = signature
    }
    
    static func ==(lhs: TypeExtension, rhs: TypeExtension) -> Bool {
        return lhs.properties == rhs.properties && lhs.methods == rhs.methods && lhs.group == rhs.group && lhs.signature == rhs.signature
    }

    public func hash(into hasher: inout Hasher) {
        hasher.combine(group)
        hasher.combine(properties)
        hasher.combine(methods)
        hasher.combine(signature)
    }
}

该类用于表示js里的对象，class，还有个FunctionSignature应该是对应js里的function，具体内容可以看FunctionSignature和Parameter类的实现

参考链接

https://github.com/googleprojectzero/fuzzilli/blob/main/Docs/HowFuzzilliWorks.md