trailofbits/necessist
GitHub: trailofbits/necessist
通过系统性地移除测试语句来识别形同虚设的测试用例，帮助开发者发现测试中的隐蔽缺陷。
Stars: 137 | Forks: 19
# Necessist
通过移除语句和方法调用来运行测试，以帮助识别有问题的测试
Necessist 目前支持 Anchor、Foundry、Go、Hardhat、Rust 和 Vitest。
一篇关于 Necessist 的论文发表于 Mutation 2024。([幻灯片], [预印本])
**目录**
- [安装](#installation)
- [运行](#running)
- [概述](#overview)
- [用法](#usage)
- [详情](#details)
- [配置文件](#configuration-files)
- [局限性](#limitations)
- [语义版本控制策略](#semantic-versioning-policy)
- [目标](#goals)
- [非目标](#anti-goals)
- [参考](#references)
- [许可证](#license)
## 安装
#### 系统要求：
在您的系统上安装 `pkg-config` 和 `sqlite3` 开发文件，例如，在 Ubuntu 上：
```
sudo apt install pkg-config libsqlite3-dev
```
#### 从 [crates.io] 安装 Necessist：
```
cargo install necessist
```
## 运行
`cd` 进入您的项目目录并输入 `necessist`（不带参数）。
例如，如果您 `cd` 进入 [`fixtures/basic`] 目录并输入 `necessist`，您应该会看到以下内容：
```
4 candidates in 4 tests in 1 source file
src/lib.rs: dry running
src/lib.rs: mutilating
src/lib.rs:4:5-4:12: `n += 1;` passed
```
请注意，当 Necessist 使用超时运行测试时会有延迟。
有关可传递给 `necessist` 的选项，请参见 [用法]。
## 概述
Necessist 迭代地从测试中移除语句和方法调用，然后运行它们。如果测试在移除语句或方法调用后通过，则可能表明测试存在问题。或者更糟的是，这可能表明被测代码存在问题。
### 示例
此示例来自 [`rust-openssl`]。`verify_untrusted_callback_override_ok` 测试检查失败的证书验证是否可以被回调覆盖。但是，如果从未调用回调（例如，由于连接失败），测试仍将通过。Necessist 通过显示测试在没有调用 `set_verify_callback` 的情况下通过来揭示这一事实：
```
#[test]
fn verify_untrusted_callback_override_ok() {
let server = Server::builder().build();
let mut client = server.client();
client
.ctx()
.set_verify_callback(SslVerifyMode::PEER, |_, x509| { //
assert!(x509.current_cert().is_some()); // Test passes without this call
true // to `set_verify_callback`.
}); //
client.connect();
}
```
在此发现之后，向测试[添加了一个标志]以记录是否调用了回调。测试成功必须设置该标志：
```
#[test]
fn verify_untrusted_callback_override_ok() {
static CALLED_BACK: AtomicBool = AtomicBool::new(false); // Added
let server = Server::builder().build();
let mut client = server.client();
client
.ctx()
.set_verify_callback(SslVerifyMode::PEER, |_, x509| {
CALLED_BACK.store(true, Ordering::SeqCst); // Added
assert!(x509.current_cert().is_some());
true
});
client.connect();
assert!(CALLED_BACK.load(Ordering::SeqCst)); // Added
}
```
### 与传统变异测试的比较
### 可能的理论基础
## 用法
```
Usage: necessist [OPTIONS] [TEST_FILES_OR_DIRS]... [-- ...]
Arguments:
[TEST_FILES_OR_DIRS]... Test files or directories to mutilate (optional)
[ARGS]... Additional arguments to pass to each test command
Options:
--allow Silence ; `--allow all` silences all warnings
--default-config Create a default necessist.toml file in the project's root directory
--deny Treat as an error; `--deny all` treats all warnings as errors
--dump Dump sqlite database contents to the console
--dump-candidate-counts Dump number of removal candidates in each file and exit
--dump-candidates Dump removal candidates and exit (for debugging)
--framework Assume testing framework is [possible values: anchor, auto, foundry, go, hardhat, rust, vitest]
--no-lines-or-columns Do not output line or column information (experimental)
--no-sqlite Do not output to an sqlite database
--quiet Do not output to the console
--reset Discard sqlite database contents
--resume Resume from the sqlite database
--root Root directory of the project under test
--timeout Maximum number of seconds to run any test; 60 is the default, 0 means no timeout
--verbose Show test outcomes besides `passed`
-h, --help Print help
-V, --version Print version
```
### 输出
默认情况下，Necessist 仅在测试通过时输出到控制台。传递 `--verbose` 会导致 Necessist 改为输出以下所有移除结果。
| 结果 | 含义（移除语句/方法调用后...） |
| -------------------------------------------- | --------------------------------------------------- |
| passed | 测试构建并通过。 |
| timed-out | 测试构建但超时。 |
| failed | 测试构建但失败。 |
| nonbuildable | 测试未构建。 |
默认情况下，Necessist 输出到控制台和 sqlite 数据库。对于后者，可以使用 [sqlitebrowser] 等工具来过滤/排序结果。
## 详情
一般来说，如果是以下情况之一，Necessist 将不会尝试移除语句：
- 包含其他语句的语句（例如，`for` 循环）
- 声明（例如，局部或 `let` 绑定）
- `break`、`continue` 或 `return`
- 测试中的最后一条语句
同样，如果是以下情况，Necessist 将不会尝试移除方法调用：
- 它是封闭语句的主要效果（例如，`x.foo();`）。
- 它出现在被忽略的函数、方法或宏的参数列表中（[见下文](#configuration-files)）。
此外，对于某些框架，某些语句和方法会被忽略。单击框架以查看其详细信息。
## 配置文件
配置文件允许人们根据项目调整 Necessist 的行为。该文件必须命名为 `necessist.toml`，出现在项目的根目录中，并进行 [toml] 编码。该文件可能包含下面列出的一个或多个选项。
- `ignored_functions`、`ignored_methods`、`ignored_macros`：解释为[模式]的字符串列表。其[路径]与列表中的模式匹配的函数、方法或宏（分别）将被忽略。请注意，`ignored_macros` 目前仅由 Rust 后端使用。
- `ignored_path_disambiguation`：字符串 `Either`、`Function` 或 `Method` 之一。对于可能引用函数或方法的[路径]（[见下文](#paths)），此选项会影响是忽略函数还是方法。
- `Either`（默认）：如果路径与 `ignored_functions` 或 `ignored_methods` 模式匹配，则忽略。
- `Function`：仅当路径与 `ignored_functions` 模式匹配时才忽略。
- `Method`：仅当路径与 `ignored_methods` 模式匹配时才忽略。
- `ignored_tests`：字符串列表。名称与列表中的字符串完全匹配的测试将被忽略。对于基于 Mocha 的框架（例如，Anchor 和 Hardhat），测试名称被视为传递给 `it` 的消息。
- `walkable_functions`：解释为[模式]的字符串列表。如果测试调用与模式匹配的函数，并且该函数在与测试相同的文件中声明，则从该函数中移除语句和方法调用，就像它是测试一样。
### 模式
模式是由字母、数字、`.`、`_` 或 `*` 组成的字符串。除 `*` 外的每个字符均按字面意思处理，并且仅与自身匹配。`*` 匹配任何字符串，包括空字符串。
以下是模式的示例：
- `assert`：仅匹配自身
- `assert_eq`：仅匹配自身
- `assertEqual`：仅匹配自身
- `assert.Equal`：仅匹配自身
- `assert.*`：匹配 `assert.Equal`，但不匹配 `assert`、`assert_eq` 或 `assertEqual`
- `assert*`：匹配 `assert`、`assert_eq`、`assertEqual` 和 `assert.Equal`
- `*.Equal`：匹配 `assert.Equal`，但不匹配 `Equal`
注意：
- 模式匹配[路径]，而不是单个标识符。
- `.` 像在 [`glob`] 模式中一样按字面意思处理，而不是像在正则表达式中那样。
### 路径
路径是由 `.` 分隔的标识符序列。考虑这个例子（来自 [Chainlink]）：
```
operator.connect(roles.oracleNode).signer.sendTransaction({
to: operator.address,
data,
}),
```
在上面，`operator.connect` 和 `signer.sendTransaction` 是路径。
但是请注意，像 `operator.connect` 这样的路径是模棱两可的：
- 如果 `operator` 引用包或模块，则 `operator.connect` 引用函数。
- 如果 `operator` 引用对象，则 `operator.connect` 引用方法。
默认情况下，如果此类路径与 `ignored_functions` 或 `ignored_methods` 模式匹配，Necessist 会忽略它。将上面的 `ignored_path_disambiguation` 选项设置为 `Function` 或 `Method` 会导致 Necessist 仅在该路径与 `ignored_functions` 或 `ignored_methods` 模式匹配（分别）时才忽略它。
## 局限性
- **慢。** 修改测试需要重新构建它们。即使在中等规模的代码库上运行 Necessist 也可能需要几个小时。
- **分类需要对源代码有深入了解。** 一般来说，Necessist 不会产生“明显”的错误。根据我们的经验，决定语句/方法调用是否必要需要对被测代码有深入了解。Necessist 最适合在拥有（或打算拥有）此类知识的代码库上运行。
## 语义版本控制策略
我们保留更改以下内容的权利，并将此类更改视为非破坏性的：
- Necessist 默认忽略的语法
对以下内容的更改将伴随着 Necessist 至少次版本号的升级：
- 输出移除候选者的顺序
- 记录在 necessist.db 中的存储顺序
## 目标
- 如果项目使用支持的框架，则 `cd` 进入项目目录并输入 `necessist`（不带参数）应产生有意义的输出。
## 非目标
- 成为通用的变异测试工具。这样的优秀工具已经存在（例如，[`universalmutator`]）。
## 参考
- Groce, A., Ahmed, I., Jensen, C., McKenney, P.E., Holmes, J.: How verified (or tested) is my code? Falsification-driven verification and testing. Autom. Softw. Eng. **25**, 917–960 (2018). [预印本可用]。参见第 2.3 节。
## 许可证
Necessist 根据 AGPLv3 许可证授权和分发。如果您正在寻找条款的例外情况，请[联系我们](mailto:opensource@trailofbits.com)。
点击展开
传统变异测试试图识别_测试覆盖率中的缺口_，而 Necessist 试图识别_现有测试中的错误_。 传统变异测试工具（如 [`universalmutator`]）随机将错误注入源代码，并查看代码的测试是否仍然通过。如果通过，则可能意味着代码的测试不充分。 值得注意的是，传统变异测试是关于发现整个测试集中的缺陷，而不是单个测试中的缺陷。也就是说，对于任何给定的测试，随机将错误注入代码并不特别可能揭示该测试中的错误。这很不幸，因为某些测试比其他测试更重要，例如，因为确保代码某些部分的正确性比其他部分更重要。 相比之下，Necessist 迭代移除语句和方法调用的方法确实针对单个测试，因此可以揭示单个测试中的错误。 当然，这两种方法可以发现的问题集存在重叠，例如，未能发现注入的错误可能表明测试中存在错误。尽管如此，出于刚才给出的原因，我们将这两种方法视为互补的，而不是竞争的。点击展开
以下准则（`*`）接近于描述 Necessist 旨在移除的语句： - （`*`）语句 `S` 的[最弱前置条件] `P` 与 `S` 的后置条件 `Q` 具有相同的上下文（例如，作用域内的变量），并且 `P` 不蕴涵 `Q`。 （`*`）试图捕捉的概念是：影响后续断言的语句。在本节中，我们解释并动机这一选择。为了简洁起见，我们关注语句，但本节中的备注也适用于方法调用。 回想一下两类[谓词转换器语义]：最弱前置条件和最强后置条件。使用前者，人们可以推理语句之前可能成立的最弱前置条件，给定语句之后成立的后置条件。使用后者，人们可以推理语句之后可能成立的最强后置条件，给定语句之前成立的前置条件。一般来说，前者更常见（有关解释，请参见 [Aldrich 2013]），并且是我们在这里使用的。 从这个角度考虑测试。测试是一个没有输入或输出的函数。因此，确定测试是否通过的替代过程如下。从 `True` 开始，向后迭代遍历测试的语句，计算每条语句的最弱前置条件。如果为测试的第一条语句到达的前置条件是 `True`，则测试通过。如果前置条件是 `False`，则测试失败。 现在，想象我们要应用此过程，并考虑违反（`*`）的语句 `S`。我们认为移除 `S` 可能没有意义： **情况 1**：`S` 在作用域中添加或移除变量（例如，`S` 是声明），或者 `S` 更改变量的类型。那么移除 `S` 可能会导致编译失败。（此外，由于 `S` 的前置条件和后置条件具有不同的上下文，尚不清楚如何比较它们。） **情况 2**：`S` 的前置条件比其后置条件更强（例如，`S` 是断言）。那么 `S` 对其执行的环境施加了约束。换句话说，`S` _测试_ 某事。因此，移除 `S` 可能会削弱测试的总体目的。 相反，考虑满足（`*`）的语句 `S`。这就是为什么移除 `S` 可能有意义的原因。将 `S` 视为_转移_ 有效环境的集合，而不是约束它们。更准确地说，如果 `S` 的最弱前置条件 `P` 不蕴涵 `Q`，并且 `Q` 是可满足的，那么存在对 `P` 和 `Q` 的自由变量的赋值，同时满足 `P` 和 `Q`。如果这种赋值是在 `S` 实际执行的每个环境中产生的，那么 `S` 的必要性就受到质疑。 （`*`）的主要效用在于帮助选择 Necessist 忽略的函数、宏和方法调用。默认情况下，Necessist 忽略其中某些。假设对于其中一个框架，我们正在考虑 Necessist 是否应忽略某个函数 `foo`。如果我们想象框架测试语言的谓词转换器语义，我们可以问：如果语句 `S` 是对 `foo` 的调用，`S` 会满足（`*`）吗？如果答案是“否”，那么 Necessist 可能应该忽略 `foo`。 以 Rust 的 `clone` 方法为例。对 `clone` 的调用可能是不必要的。但是，如果我们想象 Rust 的谓词转换器语义，对 `clone` 的调用不太可能满足（`*`）。因此，Necessist 不会尝试移除 `clone` 调用。 除了帮助选择 Necessist 忽略的函数等之外，（`*`）还有其他不错的结果。例如，测试中的最后一条语句应该被忽略的规则源于（`*`）。要看到这一点，请注意此类语句的后置条件 `Q` 始终为 `True`。因此，如果语句不更改上下文，则其最弱前置条件必然蕴涵 `Q`。 尽管如此，（`*`）并没有完全捕捉到 Necessist 实际_做_什么。考虑像 `x -= 1;` 这样的语句。Necessist 将无条件移除此类语句，但（`*`）表示也许 Necessist 不应该这样做。假设启用了[溢出检查]，计算此语句的最弱前置条件看起来类似于以下内容： ``` { Q[(x - 1)/x] ^ x >= 1 } x -= 1; { Q } ``` 请注意，`x -= 1;` 不会更改上下文，并且 `Q[(x - 1)/x] ^ x >= 1` 可能蕴涵 `Q`。例如，如果 `Q` 不包含 `x`，则 `Q[(x - 1)/x] = Q`，并且 `Q ^ x >= 1` 蕴涵 `Q`。 鉴于（`*`）与 Necessist 当前行为之间的差异，人们可以问：应该调整两者中的哪一个？换句话说，Necessist 是否应该无条件地移除像 `x -= 1;` 这样的语句？ 看待这个问题的一种方式是：哪些语句值得移除，即哪些语句是“有趣的？”如上所述，如果语句的移除可能影响后续断言，则（`*`）认为语句是“有趣的”。但是“有趣”语句还有其他可能的、有用的定义。例如，可以考虑最强后置条件（上面提到的），或者[除 Hoare 逻辑之外的框架]。 需要明确的是，Necessist 不会正式应用（`*`），例如，Necessist 实际上并不计算最弱前置条件。（`*`）目前的作用是帮助指导 Necessist 应忽略哪些语句，并且（`*`）似乎在该角色中表现良好。因此，我们将解决上述差异留给未来的工作。Anchor
除以下内容外，Anchor 后端还忽略： - `throw` 语句 #### 被忽略的函数 - `assert` - 任何以 `assert.` 开头的内容（例如，`assert.equal`） - 任何以 `console.` 开头的内容（例如，`console.log`） - `expect` #### 被忽略的方法 - `toNumber` - `toString`Foundry
除以下内容外，Foundry 后端还忽略： - 紧随使用 `vm.prank` 或任何形式的 `vm.expect`（例如，`vm.expectRevert`）之后的语句 - `emit` 语句 #### 被忽略的函数 - 任何以 `assert` 开头的内容（例如，`assertEq`） - 任何以 `vm.expect` 开头的内容（例如，`vm.expectCall`） - 任何以 `console.log` 开头的内容（例如，`console.log`、`console.logInt`） - 任何以 `console2.log` 开头的内容（例如，`console2.log`、`console2.logInt`） - `vm.getLabel` - `vm.label` - `vm.startSnapshotGas` - `vm.stopSnapshotGas`Go
除以下内容外，Go 后端还忽略： - `defer` 语句 #### 被忽略的函数 - 任何以 `assert.` 开头的内容（例如，`assert.Equal`） - 任何以 `require.` 开头的内容（例如，`require.Equal`） - `panic` #### 被忽略的方法\* - `Close` - `Error` - `Errorf` - `Fail` - `FailNow` - `Fatal` - `Fatalf` - `Helper` - `Log` - `Logf` - `Parallel` - `Skip` - `Skipf` - `SkipNow` \* 此列表主要基于 [`testing.T`] 的方法。但是，为了避免与其他类型的方法冲突，省略了一些具有常用名称的方法。Hardhat
被忽略的函数和方法与上面的 Anchor 相同。Rust
#### 被忽略的宏 - `assert` - `assert_eq` - `assert_matches` - `assert_ne` - `debug` - `eprint` - `eprintln` - `error` - `info` - `panic` - `print` - `println` - `trace` - `unimplemented` - `unreachable` - `warn` #### 被忽略的方法\* - `as_bytes` - `as_encoded_bytes` - `as_mut` - `as_mut_os_str` - `as_mut_os_string` - `as_mut_slice` - `as_mut_str` - `as_os_str` - `as_path` `as_ref` - `as_slice` - `as_str` - `borrow` - `borrow_mut` - `clone` - `cloned` - `copied` - `deref` - `deref_mut` - `expect` - `expect_err` - `into_boxed_bytes` - `into_boxed_os_str` - `into_boxed_path` - `into_boxed_slice` - `into_boxed_str` - `into_bytes` - `into_encoded_bytes` - `into_os_string` - `into_owned` - `into_path_buf` - `into_string` - `into_vec` - `iter` - `iter_mut` - `success` - `to_os_string` - `to_owned` - `to_path_buf` - `to_string` - `to_vec` - `unwrap` - `unwrap_err` \* 此列表本质上是 Dylint 的 [`unnecessary_conversion_for_trait`] lint 的监视特征和固有方法，并添加了以下内容： - `clone` (例如 [`std::clone::Clone::clone`]) - `cloned` (例如 [`std::iter::Iterator::cloned`]) - `copied` (例如 [`std::iter::Iterator::copied`]) - `expect` (例如 [`std::option::Option::expect`]) - `expect_err` (例如 [`std::result::Result::expect_err`]) - `into_owned` (例如 [`std::borrow::Cow::into_owned`]) - `success` (例如 [`assert_cmd::assert::Assert::success`]) - `unwrap` (例如 [`std::option::Option::unwrap`]) - `unwrap_err` (例如 [`std::result::Result::unwrap_err`])Vitest
被忽略的函数和方法与上面的 Anchor 相同。标签：Anchor, Debug, DNS解析, Foundry, Go, Hardhat, pocsuite3, Ruby工具, Rust, SOC Prime, Solidity, Vitest, 云安全监控, 变异测试, 可视化界面, 开发工具, 开源项目, 故障排查, 日志审计, 测试可靠性, 测试辅助工具, 网络流量审计, 软件测试, 通知系统, 通知系统, 静态分析