• 1 模糊测试的技术原理
• 2 模糊测试生成种子方法
  • 2.1 基于符号执行的方法
  • 2.2 基于污点分析的方法
  • 2.3 基于遗传变异的方法
  • 2.4 基于覆盖引导的方法
  • 2.5 基于语法树变异的方法

1 模糊测试的技术原理

通过提供大量畸形数据输入给被测程序，触发程序的崩溃或异常执行状态。它的工作流程包含如下6步：

1. 识别目标系统

   首先确定被测对象，了解被测对象的类型，比如被测目标是客户端程序还是服务端程序，二进制还是源代码，被测对象是否出现过漏洞等，了解清楚之后才可以有效地给出准确的测试计划。

2. 识别输入

   大部分可被利用的安全漏洞都是由于应用程序没有对用户的输入进行校验或没有对非法输入进行处理而造成的。是否能找到所有的输入向量 (Input vector) 是模糊测试能否成功的关键。寻找输入向量的原则是：向目标应用发送的任何东西，例如头 (Headers)、文件名 (File Name)、环境变量 (Environment variables)，注册表键 (Registry keys)，以及其他信息，都可能是潜在的模糊测试变量。

3. 生成模糊数据

   识别出输入向量后，依据测试对象的特征，制定相应的模糊测试数据生成策略。通常，可通过生成或变异己有的数据，利用程序动态运行时产生的临时数据，动态生成数据。

4. 使用模糊数据执行测试

   执行过程可能包括发送数据包给目标应用程序、打开一个文件或发起一个目标进程。同样，这个过程中的自动化也是至关重要的。

5. 监控系统行为

   在模糊测试的过程中，我们要实时监控故障或异常，及时发现问题。常用的异常监视技术依据原理分为两种：基于调试的方法和基于插桩的方法。

   基于调试的方法意在调试模式下启动目标软件，通过操作系统平台提供的调试API,开发有针对性的异常监测模块。

   插桩技术是指在保证原有程序逻辑完整性的基础上，在程序中插入探针，通过探针采集代码中的信息（方法本身、方法参数值、返回值等）并在特定的位置插入代码段，从而收集程序运行时的动态上下文信息。目前常用的插桩方法分为静态代码插桩（源代码、中间码、二进制）和二进制代码动态插桩。

6. 记录缺陷，确定可利用性

   一旦确定被测目标存在故障，则需要确定所发现的bug是否可复现，重现故障最常用的手段就是重放检测，即调用数据包重放工具将转储的网络数据包进行重放。

2 模糊测试生成种子方法

现阶段模糊测试用例的生成一般分为两类：基于生成和基于变异，总体可涵盖为诸如符号执行、污点分析、覆盖引导、语法树变异、遗传变异等。

2.1 基于符号执行的方法

该方法的核心思想是以测试用例为符号值，在处理过程中搜索测试路径上的核心约束信息。通过约束求解生成一个新的测试用例，以覆盖不同的程序执行路径。这种方法适用于测试结构简单、执行路径少的程序。

例如当前有如下一个简单的程序：

int process_input(int x, int y) {
    if (x > 10) {
        if (y < 5) {
            return x + y;
        } else {
            return x - y;
        }
    } else {
        return x * y;
    }
}

通过符号执行生成一组种子输入，以覆盖所有可能的路径。

1. 符号化输入：

   将程序的输入x和y视为符号变量X和Y，而不是具体的值。例如：

   • x = X，y = Y

   这些符号变量表示程序的输入，并用于表达路径条件。

2. 路径分析：

   逐步分析程序中的分支逻辑，收集每条路径的约束条件：

   路径1：x > 10 且 y < 5

   • 约束条件：
     • X>10
     • Y<5

   路径2：x > 10 且 y >= 5

   • 约束条件：
     • X>10X
     • Y≥5

   路径3：x <= 10

   • 约束条件：
     • X≤10

3. 求解路径约束

   对于每条路径，使用一个约束求解器（如 Z3 或其他符号执行工具）来生成满足路径约束的具体输入值。

   路径1：

   • 约束：X>10 和 Y<5
   • 示例解：X=15,Y=3

   路径2：

   • 约束：X>10 和 Y≥5
   • 示例解：X=12,Y=6X

   路径3：

   • 约束：X≤10
   • 示例解：X=8,Y=2

4. 生成种子文件

   将每条路径的具体输入保存为种子文件。例如，创建一个seeds/文件夹，其中每个种子文件的内容为一组具体输入：

   • seeds/seed1.txt:

     15 3
     

   • seeds/seed2.txt:

     12 6
     

   • seeds/seed3.txt:

     8 2
     

​ 这些文件将作为模糊测试的初始种子输入。

2.2 基于污点分析的方法

该方法的核心思想是利用动态污点分析技术标记输入数据的污染源，关注污点的传播过程，从中提取关键污点信息，并利用污点信息指导生成种子变异和相关测试用例。

例如当前有如下一个简单的程序：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void process_input(char *input) {
    char buffer[16];

    if (strlen(input) > 15) {
        printf("Input is too long!\n");
        return;
    }

    strcpy(buffer, input);  // 潜在的缓冲区溢出漏洞

    if (strcmp(buffer, "admin") == 0) {
        printf("Welcome, admin!\n");
    } else {
        printf("Hello, %s\n", buffer);
    }
}

int main() {
    char input[64];
    printf("Enter your input: ");
    fgets(input, sizeof(input), stdin);

    input[strcspn(input, "\n")] = '\0'; // 去掉换行符
    process_input(input);

    return 0;
}

动态污点分析的过程

1. 污点源标记

   将程序输入（如stdin、文件、网络数据）视为污点源。在这个例子中，fgets(input, ...)接收到的input是污点数据。

   污点标记：

   • 程序中，input数组的内容被标记为污点。
   • 使用动态分析工具追踪input的数据流向。

2. 污点传播追踪

   动态追踪污点数据在程序中的传播路径。例如：

   • input被传递给process_input()，因此进入了函数的input参数。
   • 通过strcpy(buffer, input)，污点传播到了buffer。
   • 在条件判断strcmp(buffer, "admin")中，污点数据参与了敏感操作（条件判断、函数调用）。

3. 提取关键污点信息

   污点流：

   • 污点从input传播到buffer，最终影响到strcmp。

   敏感操作点：

   • 污点数据参与了strcmp的条件判断。
   • 污点数据可能导致strcpy中的缓冲区溢出（如果输入超过了buffer的大小）。

   通过这些信息，我们可以得出：

   1. 如果输入长度超过15字节，可能导致缓冲区溢出。
   2. 如果输入为admin，程序会进入特殊逻辑。

4. 生成种子变异

   利用污点信息指导生成测试用例或变异种子，覆盖程序的不同逻辑路径和潜在漏洞点：

   • 生成种子1

     输入长度为16字节（触发缓冲区溢出）。例如：

     "AAAAAAAAAAAAAAAA"
     

   • 生成种子2：输入为admin，触发管理逻辑路径。

     admin
     

   • 生成种子3

     其他输入路径，如非管理员输入。输入：

     "guest123"
     

   这些种子输入可以作为模糊测试工具（如AFL）的初始种子，或者直接用于漏洞检测。

2.3 基于遗传变异的方法

遗传变异算法利用生物进化的一些核心规则来指导模糊测试样本的生成。目前，遗传算法是应用最广泛、性能最好的进化算法，其核心思想是对测试用例进行多轮迭代变异，剔除不符合要求的测试用例或从中选出性能最好的样本作为下一轮变异的种子。遗传算法不仅可以生成新的测试用例，还可以简化样本集，从而进一步提高模糊测试的效率。

例如当前有如下一个简单的程序：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void process_input(char *input) {
    if (strcmp(input, "admin") == 0) {
        printf("Welcome, admin!\n");
    } else if (strcmp(input, "password123") == 0) {
        printf("Access granted.\n");
    } else if (strlen(input) > 16) {
        printf("Input too long! Potential overflow.\n");
    } else {
        printf("Hello, %s\n", input);
    }
}

int main() {
    char input[64];
    printf("Enter input: ");
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = '\0'; // Remove newline character
    process_input(input);
    return 0;
}

目标：

1. 通过遗传变异生成测试用例，覆盖程序中的所有条件分支。
2. 尝试发现潜在的缓冲区溢出问题。

遗传变异方法的实现步骤

1. 初始化种群：创建一个初始种群，每个个体（测试用例）是一个字符串。

   import random
   import string
      
   # 初始化种群
   def initialize_population(size, length):
       return [''.join(random.choices(string.ascii_letters + string.digits, k=length)) for _ in range(size)]
      
   population = initialize_population(size=10, length=8)
   print("Initial population:", population)
      
      
   #结果
   Initial population: ['WblrNXxq', 'QFmLTZlN', 'IxH5riq0', 'Yl0ajIYU', 'LFCM8R10', 'SKUNtcY0', 'tyyueqru', '8G8wsaRb', 'bbTXooZr', '8HAXSNUd']
   

2. 适应度函数

   设计适应度函数，用于评估每个测试用例的好坏。适应度值越高，测试用例越优。

   目标是生成能覆盖更多路径的测试用例。

   适应度函数可以基于：

   1. 程序执行路径的覆盖率。
   2. 是否触发特殊条件（如输入匹配"admin"或超过16字节）。

   def fitness_function(test_case, program_behavior, return_code):
       """
       根据程序行为评估测试用例的适应度。
       """
       if "Crash detected" in program_behavior or return_code < 0:
           return 100  # 崩溃得高分
       elif "Input too long!" in program_behavior:
           return 50  # 长输入提示
       else:
           return len(set(test_case))  # 多样性得分
      
      
   

3. 选择

   基于适应度值选择下一代的种子。

   def select(population, fitness_scores):
       total_fitness = sum(fitness_scores)
       probabilities = [score / total_fitness for score in fitness_scores]
       selected = random.choices(population, weights=probabilities, k=len(population))
       return selected
      
   

4. 交叉

   从父代中选择两个个体，进行交叉，生成新个体。

   def crossover(parent1, parent2):
       point = random.randint(1, len(parent1) - 2)
       child = parent1[:point] + parent2[point:]
       return child
   

5. 变异

   对个体进行随机变异（如随机修改字符）。

   def mutate(test_case, mutation_rate=0.1, length_mutation_rate=0.2, max_length=100):
       test_case = list(test_case)
       for i in range(len(test_case)):
           if random.random() < mutation_rate:
               test_case[i] = random.choice(string.ascii_letters + string.digits)
       if random.random() < length_mutation_rate:
           if random.random() < 0.5 and len(test_case) > 1:  # 减少长度
               test_case.pop(random.randint(0, len(test_case) - 1))
           elif len(test_case) < max_length:  # 增加长度
               test_case.extend(random.choices(string.ascii_letters + string.digits, k=random.randint(1, 10)))
       # 增加经典模式
       if random.random() < 0.1:
           test_case.extend("A" * random.randint(20, 100))  # 经典溢出模式
       return ''.join(test_case)
      
   

6. 遗传算法流程

   整合遗传算法的各个步骤，迭代生成新的测试用例。

   def genetic_algorithm(program_path, max_generations=20, population_size=10, mutation_rate=0.1):
       population = initialize_population(population_size, length=8)
       for generation in range(max_generations):
           print(f"Generation {generation + 1}:")
           fitness_scores = []
           for test_case in population:
               # 调用目标程序
               program_behavior, return_code = simulate_program_behavior(test_case, program_path)
               fitness = fitness_function(test_case, program_behavior, return_code)
               fitness_scores.append(fitness)
      
           # 输出最佳个体
           best_fitness = max(fitness_scores)
           best_test_case = population[fitness_scores.index(best_fitness)]
           print(f"  Best test case: {best_test_case}, Fitness: {best_fitness}")
      
           # 如果发现高风险行为，记录日志
           if best_fitness >= 100:
               with open("fuzzing_results.log", "a") as log_file:
                   log_file.write(f"Potential vulnerability found with input: {best_test_case}\n")
                   log_file.write(f"Program behavior: {program_behavior}\n")
      
           # 选择、交叉和变异
           population = select(population, fitness_scores)
           new_population = []
           for _ in range(len(population) // 2):
               parent1, parent2 = random.sample(population, 2)
               child1 = crossover(parent1, parent2)
               child2 = crossover(parent2, parent1)
               new_population.extend([child1, child2])
           population = [mutate(child, mutation_rate) for child in new_population]
   

7. 运行

   # 模拟程序行为（简单模拟处理逻辑）
   def simulate_program_behavior(input_str, program_path):
       """
       调用目标程序，并捕获其输出或异常。
       """
       try:
           result = subprocess.run(
               [program_path], 
               input=input_str.encode(), 
               capture_output=True, 
               timeout=1
           )
           return result.stdout.decode('utf-8'), result.returncode
       except subprocess.CalledProcessError as e:
           return f"Crash detected: {e.returncode}", -1
       except Exception as e:
           return f"Unhandled exception: {str(e)}", -1
      
   # 运行遗传算法
   program_path = "./vulnerable_program"  # 目标C程序的路径
   genetic_algorithm(program_path, max_generations=20, population_size=10, mutation_rate=0.2)
      
   

2.4 基于覆盖引导的方法

覆盖引导的模糊测试是一种有效的测试技术，它已从各种软件应用程序中检测到了十万个缺陷。它专注于最大化代码覆盖率，以在模糊测试期间发现更多缺陷。AFL工具就采用了该技术。

初始种子生成->执行测试用例->覆盖信息分析->优先变异高价值测试用例->循环迭代

例如当前有如下一个简单的程序：

#include <stdio.h>
#include <string.h>

void process_input(const char *input) {
    char buffer[16]; // 定义长度为16的缓冲区

    // 模拟潜在的溢出漏洞
    strcpy(buffer, input);

    if (strcmp(buffer, "admin") == 0) {
        printf("Welcome, admin!\n");
    } else {
        printf("Hello, %s\n", buffer);
    }
}

int main() {
    char input[64];
    printf("Enter input: ");
    fgets(input, sizeof(input), stdin);

    // 去掉输入末尾的换行符
    input[strcspn(input, "\n")] = '\0';

    process_input(input);

    return 0;
}

1. 使用 strcpy 将 input 拷贝到 buffer，但 buffer 的长度只有 16。
2. 如果输入超过 16 字节，会发生缓冲区溢出。

1. 模拟目标程序行为

   def simulate_program_behavior(input_str):
       """
       模拟程序行为，检测缓冲区溢出及路径触发情况。
       """
       coverage = set()
       buffer_size = 16  # 模拟 buffer 的大小
      
       if len(input_str) > buffer_size:
           coverage.add("buffer_overflow")  # 记录溢出路径
           return f"Buffer overflow detected with input: {input_str}", coverage
      
       if input_str == "admin":
           coverage.add("branch_admin")
           return "Welcome, admin!", coverage
       else:
           coverage.add("branch_default")
           return f"Hello, {input_str}", coverage
      
   

2. 测试执行

   def execute_test_case(test_case, known_coverage):
       """
       执行测试用例，记录新覆盖的路径。
       """
       output, coverage = simulate_program_behavior(test_case)
       new_coverage = coverage - known_coverage  # 计算新覆盖的部分
       return output, new_coverage, coverage
      
   

3. 主流程

   import random
   import string
      
   def mutate(test_case, mutation_rate=0.2, max_length=32):
       """
       随机变异测试用例，允许修改内容和长度。
       """
       test_case = list(test_case)
      
       # 修改字符内容
       for i in range(len(test_case)):
           if random.random() < mutation_rate:
               test_case[i] = random.choice(string.ascii_letters + string.digits)
      
       # 随机修改长度
       if random.random() < mutation_rate:
           if random.random() < 0.5 and len(test_case) > 1:
               test_case.pop(random.randint(0, len(test_case) - 1))  # 减少长度
           elif len(test_case) < max_length:
               test_case.append(random.choice(string.ascii_letters + string.digits))  # 增加长度
      
       return ''.join(test_case)
      
   def coverage_guided_fuzzing():
       """
       基于覆盖引导的模糊测试主流程。
       """
       # 初始化
       seed_inputs = ["admin", "test", "a" * 16]  # 种子测试用例
       known_coverage = set()
       queue = list(seed_inputs)  # 待测试的输入队列
      
       for generation in range(10):  # 限制测试代数
           print(f"Generation {generation + 1}:")
           next_queue = []
      
           for test_case in queue:
               # 执行测试用例
               output, new_coverage, coverage = execute_test_case(test_case, known_coverage)
      
               # 输出结果
               print(f"  Test case: {test_case}, Output: {output}")
               print(f"  New coverage: {new_coverage}")
      
               # 更新覆盖信息
               if new_coverage:
                   known_coverage.update(new_coverage)
                   next_queue.append(test_case)  # 优先变异新覆盖测试用例
      
               # 变异测试用例
               mutated_case = mutate(test_case)
               next_queue.append(mutated_case)
      
           # 更新队列
           queue = next_queue
      
       print(f"Final coverage: {known_coverage}")
      
   

4. 可能的结果

   Generation 1:
     Test case: admin, Output: Welcome, admin!
     New coverage: {'branch_admin'}
     Test case: test, Output: Hello, test
     New coverage: {'branch_default'}
     Test case: aaaaaaaaaaaaaaaa, Output: Hello, aaaaaaaaaaaaaaaa
     New coverage: set()
      
   Generation 2:
     Test case: aaaaaaaaaaaaaaaaaaaa, Output: Buffer overflow detected with input: aaaaaaaaaaaaaaaaaaaa
     New coverage: {'buffer_overflow'}
     Test case: aaaaaaaabaaaaaaa, Output: Hello, aaaaaaaabaaaaaaa
     New coverage: set()
      
   Final coverage: {'branch_admin', 'branch_default', 'buffer_overflow'}
      
   

2.5 基于语法树变异的方法

语法树是源代码语法结构的一种表示，它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。而语法树变异是基于变异生成种子文件相应的语法树，然后以其子树为对象进行替换操作。替换的材料可能由用户指定，也可能由系统按照一定规则自动生成。

错误程序

import ast
import operator

def evaluate_expression(expr):
    """
    解析并计算数学表达式。
    输入：
      - expr: 字符串形式的数学表达式（如 "1 + 2 * 3"）
    返回：
      - 表达式的计算结果。
    """
    try:
        # 将表达式解析为语法树
        tree = ast.parse(expr, mode='eval')

        # 评估表达式
        return eval(compile(tree, filename="", mode="eval"))
    except Exception as e:
        # 捕获异常，返回错误信息
        return f"Error: {str(e)}"

1.解析表达式为语法树

import ast

expr = "1 + 2 * 3"
tree = ast.parse(expr, mode="eval")
print(ast.dump(tree, indent=4))

Expression(
    body=BinOp(
        left=Constant(value=1),
        op=Add(),
        right=BinOp(
            left=Constant(value=2),
            op=Mult(),
            right=Constant(value=3))))

语法树变异

可以通过以下方法对语法树进行变异：

1. 替换操作符：将 + 替换为 *、- 或 /。
2. 调整常量值：对常量值加减一定范围的偏移。
3. 插入子表达式：在某个节点下插入新的子表达式（如 x + y）。
4. 删除子表达式：移除部分节点，生成简化的表达式。

完整程序以及运行结果

import ast
import random
import ast
import operator

def evaluate_expression(expr):
    """
    解析并计算数学表达式。
    输入：
      - expr: 字符串形式的数学表达式（如 "1 + 2 * 3"）
    返回：
      - 表达式的计算结果。
    """
    try:
        # 将表达式解析为语法树
        tree = ast.parse(expr, mode='eval')

        # 评估表达式
        return eval(compile(tree, filename="", mode="eval"))
    except Exception as e:
        # 捕获异常，返回错误信息
        return f"Error: {str(e)}"

class ExpressionMutator(ast.NodeTransformer):
    """
    对表达式的语法树进行变异操作。
    """

    def visit_BinOp(self, node):
        """
        处理二元运算符节点，随机替换运算符或变异子表达式。
        """
        # 随机变异操作符
        if random.random() < 0.5:
            node.op = random.choice([ast.Add(), ast.Sub(), ast.Mult(), ast.Div()])

        # 递归变异子表达式
        self.generic_visit(node)
        return node

    def visit_Constant(self, node):
        """
        处理常量节点，随机调整常量值。
        """
        if isinstance(node.value, (int, float)) and random.random() < 0.5:
            node.value += random.randint(-10, 10)
        return node

def mutate_expression(expr):
    """
    将表达式解析为语法树，进行变异后返回新表达式。
    """
    # 解析表达式为语法树
    tree = ast.parse(expr, mode="eval")

    # 对语法树进行变异
    mutator = ExpressionMutator()
    mutated_tree = mutator.visit(tree)

    # 将变异后的语法树转回表达式字符串
    ast.fix_missing_locations(mutated_tree)
    mutated_expr = ast.unparse(mutated_tree)
    return expr, mutated_expr

def fuzz_test_with_ast():
    """
    基于语法树变异的模糊测试主流程。
    """
    seed_inputs = ["1 + 2 * 3", "4 / 2 + 6", "(1 + 2) * (3 - 4)"]  # 初始种子输入
    tested_cases = set()  # 已测试的用例

    for generation in range(5):  # 限制测试代数
        print(f"Generation {generation + 1}:")
        next_inputs = []

        for seed in seed_inputs:
            if seed in tested_cases:
                continue

            # 对种子输入进行变异
            try:
                original_expr, mutated_expr = mutate_expression(seed)
                print(f"  Original: {original_expr}, Mutated: {mutated_expr}")
            except Exception as e:
                print(f"  Error in mutation: {e}")
                continue

            # 执行变异后的表达式
            result = evaluate_expression(mutated_expr)
            print(f"    Result: {result}")

            # 检查是否发现异常行为
            if isinstance(result, str) and "Error" in result:  # 确保 result 是字符串
                print(f"    Potential issue detected with input: {mutated_expr}")

            # 添加到下一轮输入队列
            next_inputs.append(mutated_expr)

            # 记录已测试用例
            tested_cases.add(seed)

        seed_inputs = next_inputs  # 更新输入队列


fuzz_test_with_ast()

运行结果

Generation 1:
  Original: 1 + 2 * 3, Mutated: 1 / (2 * 12)
    Result: 0.041666666666666664
  Original: 4 / 2 + 6, Mutated: 0 * 2 - 6
    Result: -6
  Original: (1 + 2) * (3 - 4), Mutated: (1 + 2) * (3 - 9)
    Result: -18
Generation 2:
  Original: 1 / (2 * 12), Mutated: 8 / (11 / 12)
    Result: 8.727272727272728
  Original: 0 * 2 - 6, Mutated: 0 * -6 - -3
    Result: 3
  Original: (1 + 2) * (3 - 9), Mutated: (1 + 2) / (13 + 9)
    Result: 0.13636363636363635
Generation 3:
  Original: 8 / (11 / 12), Mutated: 8 - 1 * 12
    Result: -4
  Original: 0 * -6 - -3, Mutated: -3 * -6 * -3
    Result: -54
  Original: (1 + 2) / (13 + 9), Mutated: 1 * -7 / (19 - 19)
    Result: Error: division by zero
    Potential issue detected with input: 1 * -7 / (19 - 19)
Generation 4:
  Original: 8 - 1 * 12, Mutated: 8 / (-8 * 4)
    Result: -0.25
  Original: -3 * -6 * -3, Mutated: -3 * -6 * -8
    Result: -144
  Original: 1 * -7 / (19 - 19), Mutated: -9 / -9 / (19 - 19)
    Result: Error: float division by zero
    Potential issue detected with input: -9 / -9 / (19 - 19)
Generation 5:
  Original: 8 / (-8 * 4), Mutated: 5 / (-0 + 2)
    Result: 2.5
  Original: -3 * -6 * -8, Mutated: (-7 - -6) * -8
    Result: 8
  Original: -9 / -9 / (19 - 19), Mutated: (-4 + -9) / (21 - 19)
    Result: -6.5