北大李戈团队提出：利用分片思想生成复杂函数的单测方法

标签：李戈 -- 代码 value method 单测 分片 total 复杂度

单元测试的目标是：通过对代码的最小单位进行独立测试，提高代码的可靠性，降低引入新错误的风险，确保代码功能的正确性，并提供一种持续验证的机制，帮助开发者保持代码的高质量和可维护性。

环复杂度

对待测函数的复杂度，有个指标：环复杂度，也称为圈复杂度或圈复杂度度量（Cyclomatic Complexity，简称 CC），是衡量一个程序的逻辑复杂度的指标。

它表示程序的独立路径数量，或者说是代码中可能存在的独立执行路径的数量。

它的计算基于程序的控制流图（Control Flow Graph），通过分析代码中的分支、循环、条件语句等控制结构来确定，环复杂度的计算公式：

CC=E−N+2P

其中：

• 是控制流图中的节点数。控制流图中的每一个节点对应于程序中的某些基本执行块（如一段没有分支的代码）。每个节点之间通过控制流（边）相连。比如一个简单的赋值语句或输出语句通常可以被认为是一个节点。

• 是控制流图中的边数。边代表从一个节点到下一个节点的控制流。例如，一个 if-else 语句就会产生两条边，分别对应于条件成立时和条件不成立时的两个不同路径。

• 是程序中独立的流程分支（例如子程序或函数）。对于大多数程序或函数来说，独立的流程分支通常是 1（即从唯一的入口开始执行）。但如果程序中有多个函数或子程序，独立流程分支的数量会增加。

假设我们有以下一段简单的代码：

def process_data(data):
    if data is None:
        return "No data"
    
    total = 0
    index = 0
    
    while index < len(data):
        value = data[index]
        if value > 100:
            total += value
        elif value > 50:
            total += value / 2
        else:
            total += 1
        
        if value % 2 == 0:
            total *= 2
        
        index += 1
    
    if total > 1000:
        return "High"
    elif total > 500:
        return "Medium"
    else:
        return "Low"

这段代码的控制流图如下：

graph TD; A[Start] --> B{"data is None?"}; B -->|Yes| C["return 'No data'"]; B -->|No| D["total = 0, index = 0"]; D --> E{"index < len(data)?"}; E -->|No| F{"total > 1000?"}; E -->|Yes| G["value = data[index]"]; G --> H{"value > 100?"}; H -->|Yes| I["total += value"]; H -->|No| J{"value > 50?"}; J -->|Yes| K["total += value / 2"]; J -->|No| L["total += 1"]; I --> M{"value % 2 == 0?"}; K --> M; L --> M; M -->|Yes| N["total *= 2"]; M -->|No| O; N --> O; O --> P["index += 1"]; P --> E; F -->|Yes| Q["return 'High'"]; F -->|No| R{"total > 500?"}; R -->|Yes| S["return 'Medium'"]; R -->|No| T["return 'Low'"];

上面代码的环复杂度为：

• 节点数 (N)： 20
• 边数 (E)： 23
• 程序只有一个入口点，所以 P = 1。

CC=E(23)−N(20)+2P(1) = 5

通常来说，环复杂度越高，代码的可测试性、可维护性和错误率都会受到影响。一般的经验法则是，环复杂度为 1 表示线性代码，没有条件或循环，数值越高，意味着代码中有更多的分支或循环。

当环复杂度大于 10 时，意味着这个函数或代码片段中包含了相当多的条件分支、循环、或是多重嵌套的逻辑路径。这种情况下，生成高覆盖率的测试样例变得非常困难，因为要确保每一个独立路径都得到充分测试，可能需要非常多的测试样例。复杂度越高，路径的组合数量呈指数增长，因此大模型（例如大语言模型或生成模型）生成覆盖所有路径的测试集就变得非常具有挑战性。

利用分片思想生成复杂函数的单测

随着AI的进步，让AI产生单测会提效很多。
但是大模型自身无力为复杂待测函数（环复杂度大于10）生成高覆盖率的测试样例。针对该痛点，北京大学李戈教授团队提出一种方法切片的解决方案 HITS （High-coverage LLM-based Unit Test Generation via Method Slicing 基于方法切片的高覆盖率LLM单元测试生成）：

将复杂的方法分解成多个切片（小块）。然后，逐个切片让LLM生成相应的测试用例。

通过这种方法，LLM的分析范围得到了简化，使其更容易覆盖每个切片中的更多代码行和分支。

相关论文:

https://arxiv.org/pdf/2408.11324

主线流程：

1、程序分片

程序分片指将一个程序依据语义划分为若干解决问题的阶段。程序是对一个问题解决方案的形式化表述。一个问题解决方案通常包含多个步骤，每个步骤对应着程序中的一片（slice）代码。

如下图所示，一个色块对应着一片代码，也对应着一个问题解决的步骤。

该论文给出的程序分片的Prompt如下：

Please help me break down the method under test into
multiple slices
Here are the basic details about the method under test
{{ focal method }}
{{ dependencies }}
Please decompose the method under test following the
instructions
1. Summarise the focal method
2. List necessary env settings to run the focal method
- Invoked paremeters and fields
- Invoked methods
3. Decompose the focal method into multiple problemsovling steps
3.1 describe the subtask of the slice
3.2 replicate the corresponding code statements
Please output following the fomart:
...

2、构造prompt指示大模型生成初始测试样例

接下来，构建思维链（Chain-of-thought）形式的prompt引导大模型生成测试样例，推理步骤如下：

1. 列举该代码块中使用的所有变量和方法：
2. 分析并列举该代码块需要处理的所有类型的条件。
3. 对于代码块中的每个条件，设计测试用例以涵盖对应的所有代码行。注意要针对每个条件组，推断如何构造方法的输入参数和依赖的对象或类。

对应Prompt如下：

Please help me generate tests to fully cover a slice
Here are the basic details about the slice under test
{{ focal method }}
{{ dependencies }}
{{ invoked parameters, fields, methods}}
{{ slice }}
Please generate a whole unit test file covering all branches of
the slice following the giving steps
1. Enumerate all used variables and methods wiithin this block:
2. Analyze and enumerate all types of conditions that this block
is expected to handle. For instance:
... ( the example )
3. For each condition within the block, devise test cases to
encompass all corresponding lines. To achieve this:
For each condition group, infer how to construct the method's
input parameters and dependent objects and classes. For example:
... ( the example
#### Requirements and Attention for the Unit Test to Generate:...
#### Guidelines for Generating Unit Tests with Comprehensive
Coverage and Error-Free Execution: ...
### Examples
### Output Format:
...

3、通过后处理和self-debug使大模型生成的测试样例得以正确运行

大模型生成的测试样例往往难以直接使用，会出现各式各样的编译错误和来自于错误编写测试样例导致的运行时错误。

研究团队根据自身观察及已有论文的总结，设计了若干规则和常见错误的修复案例。

首先尝试依据规则修复。如果规则无法修复，则使用大模型self-debug的功能进行修复，在prompt中提供了常见错误的修复案例以供大模型参考。

Prompt中修复单元测试的步骤也是用的思维链方式的：

1. 找出发生错误的语句
2. 解释错误的原因
3. 给出如何修复错误的解决方案
4. 提供完整的修复单元测试，使用JUnit 5。

对应Prompt如下：

{{ focal method}}
{{ dependencies}}
Please help me fix the non-executable tests
{{ non-executable unit tests }}
{{ error information}}
# Procedures for Fixing the Unit Test:
Let's proceed step by step:
Please output following the fomart:
1. Pick out the statements that the errors occur
2. Explain the causes of the errors
3. Give solutions on how to fix the errors
3. Provide the complete fixed unit test, utilizing JUnit 5.
# Requirements and Considerations for the Unit Test Fix:
...
# Tips for Fixing the Unit Test: ...
# Examples of Healthy Unit Tests: ...
# Output Format
To facilitate generating the desired unit test, follow
these instructions: ...

效果

实验结果表明，与当前最先进的测试生成方法以及Evosuite等传统SBST（基于搜索的软件测试）方法相比，HITS方法在代码行和分支覆盖率方面有显著提升。

论文中给出了一个演示Case：

基线方法生成的测试样例未能完全覆盖Slice 2中的红色代码片段。

然而，HITS由于聚焦于Slice 2，对其所引用的外部变量进行了分析，捕捉到 “如果要覆盖红色代码片段，变量‘arguments’ 需要非空”的性质，根据该性质构建了测试样例，成功实现了对红色区域代码的覆盖。

标签：李戈,--,代码,value,method,单测,分片,total,复杂度
From： https://www.cnblogs.com/ghj1976/p/18400602/bei-da-li-ge-tuan-dui-ti-chu-li-yong-fen-pian-s