2021, Vol. 30
RISC-V是一个基于精简指令集(RISC)原则的开源指令集架构, 因其精简、开放、模块化的设计和高可定制的特点在工业界和教育界广受欢迎. 随着面向RISC-V的处理器接连问世, 围绕RISC-V建设完善的软件生态系统将会大大提高系统和应用软件的设计开发效率, 并降低其维护成本.
在面向RISC-V的软件开发过程中, 尤其是基于扩展指令 (例如向量扩展指令或用户自定义指令) 进行程序开发时, 很难避免以手写汇编的方式为程序编写高效的汇编代码. 例如, 为标准的C函数库编写相应的向量版本函数. 与编译器自动生成的代码不同, 手工开发的汇编代码虽然可以最大限度地提高程序的效率, 但绕过了编译时对程序的约束 (如类型检查[1]、寄存器分配[2]等), 因而对开发者提出了更高的要求. 如果开发者经验不足或对指令的理解有误, 将会为代码的正确性和安全性埋下隐患. 以向量扩展指令为例, 为常用函数 (如strlen、memcpy等) 的标准版本开发相应的向量版本后, 能否快速地、自动化地测试向量版本与标准版本的函数在语义上是否等价, 将大大影响代码的正确性和软件开发和调试的效率.
1.2 研究现状国内外学者已提出多种程序测试方法[3-5], 主要分为静态和动态两种测试思路: (1) 静态测试利用形式化的方法[6] (如符号执行[7]等), 通过对程序语句的语义建模, 模拟程序的执行, 从而达到对程序正确性的验证. 该方法不依赖指令的软硬件运行环境, 能够对程序的分支进行全覆盖从而达到严格的验证结果, 但随着程序规模的扩大, 静态方法的运算量呈现指数级增长. 因别名、分支条件不可解等因素而被迫对程序采取保守的建模方式, 也会为静态分析带来大量误报[8]; (2) 动态测试 (如模糊测试[9]等) 给定程序的输入值, 运行测试程序以触发程序中的错误. 虽有效避免了误报, 但在程序分支的覆盖率上往往很难匹及静态方法. 此外, 学术界也利用静态和动态相结合的方式[10,11]对软件测试提供新的思路. CASM-Verify[11]结合随机测试和符号执行验证密码算法在X86_64和SSE的汇编实现上的等价性, 但缺乏针对RISC-V的支持.
目前, 面向RISC-V的指令或系统级软件模拟器(如Spike、Qemu[12]、Ovpsim等) 可以为程序提供动态测试环境. 针对某段待测试的汇编程序, 并给定输入值和期望的输出值, 开发者能够在模拟器上对汇编程序进行功能级测试. 例如, Ovpsim提供了以测试用例为主导的测试脚本, 开发者可以通过将程序的运行结果 (某些寄存器或内存的值) 与参考值进行比对, 以达到测试的目的. 然而, 这种方式并无法满足语义等价性测试的需求, 因为: (1) 现有框架只针对单一测试程序, 缺乏对多个程序语义等价性测试的框架; (2) 比对程序的实际输出值与参考值, 并不足以支持语义等价性测试, 指令运行过程中产生的副作用 (如是否更改了其他寄存器和内存的值) 并未纳入考虑, 将为程序的正确性和安全性埋下隐患.
本研究基于模拟器的动态测试环境, 聚焦于设计并实现一套面向RISC-V的汇编程序语义等价性自动化测试系统, 旨在提高RISC-V汇编程序的开发与测试效率. 针对已有框架的不足, 本文设计并实现了针对多个RISC-V汇编程序语义等价性的测试框架. 系统可通过跟踪机器状态, 捕获程序执行的副作用, 并结合用户定义的测试目标生成测试报告. 实验表明, 本系统相比已有的测试系统, 能够有效地对RISC-V汇编程序的语义等价性进行测试.
本文结构如下: 第2节简要介绍了RISC-V的应用程序二进制接口; 第3节对本文研究的问题进行形式化描述; 第4节和第5节分别对系统设计和系统实现进行详细介绍; 第6节介绍了实验设计及结果并进行了案例分析; 第7节进行了总结和展望.
2 RISC-V的应用程序二进制接口本节以RV64G默认的LP64D规范为例, 简要介绍RISC-V的应用程序二进制接口 (Application Binary Interface, ABI). ABI规定了RISC-V二进制的寄存器规范、运行时栈的空间分布、函数调用规范、C语言类型细节、ELF文件格式、寻址方式等, 影响了编译工具链中指令生成、寄存器分配、ELF文件生成等诸多方面. 了解ABI规范对于汇编程序的测试至关重要, 例如返回值的传递规范将影响程序的观测值的选定. 本节简要介绍其中寄存器规范、运行时栈分布和函数调用规范3个方面.
2.1 寄存器规范依照LP64D规范, RISC-V的通用寄存器包含32个整型寄存器, 32个浮点寄存器和32个向量寄存器.
32个整型寄存器中, 0号寄存器x0恒为全0; 16个为调用者负责保存 (caller-saved) , 寄存器值在函数调用之后的值可能被修改; 16个为被调用者负责保存 (callee-saved) , 寄存器值在函数调用之后不会更改. 其中x10–x17共8个寄存器为参数寄存器 (即a0–a7寄存器); 32个浮点寄存器中, 20个为caller-saved, 12个为caller-saved, 同样具有8个参数寄存器; 32个向量寄存器 (以及vl、vtype等) 均为caller-saved.
2.2 运行时栈的空间分布运行时栈负责维护函数执行时传递的参数、临时变量、callee-saved寄存器等. 依照LP64D规范, 运行时栈空间从高地址向低地址生长, 以16字节对齐. 具体的空间分布如图1所示.
|
图 1 RISC-V运行时栈的空间分布示意图 |
2.3 函数调用规范
函数调用规范 (calling convention) 主要规定函数调用时参数和返回值如何传递, 本节依照LP64D, 主要分为5部分进行介绍: 整型参数、浮点参数、结构体参数、变长参数和返回值.
整型参数传递的主要原则是: 对于大小不超过64 bit的参数, 使用单个整型参数寄存器; 对于大小在64 bit和128 bit之间的参数, 使用连续的两个整型参数寄存器, 低64 bit和高64 bit分别放在寄存器x(n)和x(n+1)中, 若仅剩一个整型参数寄存器, 低位使用寄存器, 高位则使用栈传递; 若无可用的整型参数寄存器, 使用栈传递, 参数自右向左依次压栈.
浮点参数传递的主要原则是: 对于大小不超过64 bit的参数, 使用单个浮点参数寄存器, 不足64 bit的浮点数进行1扩展; 若无可用的浮点参数寄存器, 使用整型参数寄存器代替; 若无可用的整型参数寄存器, 将参数自右向左压栈.
结构体参数传递的主要原则是: 若结构体无浮点数成员, 可看作1个整型参数, 依照整型参数传递原则处理, 结构体内存分布不变; 若仅包含1个(或2个)成员, 均为浮点数且均为超过64 bit, 则使用1个(或2个)浮点参数寄存器传递; 若仅包含1个整型成员和1个浮点成员, 均不超过64 bit, 则分别使用1个整型和1个浮点参数寄存器传递; 其余情况均参照整型参数传递原则.
C语言中的变长参数分为有名和无名参数, 无名参数以省略号代替, 其类型和个数编译时未知, 由调用者通知被调用者本次调用的参数类型和个数(例如printf以格式化字符串的形式), 并默认执行参数的类型提升(例如将float提升为double). 变长参数传递的不同之处在于: 使用连续的两个寄存器传递64 bit至128 bit的参数时, 第1个寄存器必须为偶数号; 被调用者先将所有使用寄存器传递的无名参数进行压栈, 并计算首个无名参数在栈中的地址.
返回值可看作被调用者向调用者传递的参数, 以前两个参数寄存器传递返回值. 如果返回值超过128 bit (需要以指针的方式间接传递), 调用者负责为返回值在栈中分配空间, 并隐式地将其在栈中的地址作为第1个参数传递, 实际的参数依次后移.
3 问题描述 3.1 机器状态模型一个简单的机器状态模型可将机器状态m用一系列的“键-值”对(k, v)来描述. 即:
| $m = \{ ({k_1},{v_1}),({k_2},{v_2}),\cdots\} $ |
同时, 值v可由下式表示:
| $v = m[k],\;{\rm{ if }}(k,v) \in m$ |
其中, 键k可由寄存器名称或内存地址构成, 值v可由十六进制数字表示. 例如, 可将值为0xffff的寄存器x1表示为 (x1, 0xffff), 值为0x17的内存地址0x7f7e9b18表示为(0x7f7e9b18, 0x17).
给定程序p和初始 (输入) 机器状态mI, 机器可通过运行p得到新的 (输出) 机器状态mO, 该过程可用p(mI)=mO表示.
3.2 一般的程序测试模型我们将一般的基于测试用例的程序测试 (简称一般测试) 模型描述为: 对程序p输入一组初始机器状态, 并设置相对应的期望输出的机器状态, 通过判断以下关系是否成立以测试程序p的正确性:
| $\forall i \in \{ 0,1,\cdots,n\} ,\;p\left( {m_i^{\rm I}} \right) = m_i^{\rm O}$ |
实践中, 输入的机器状态可由测试的运行环境 (初始化程序、输入参数等) 给定, 而期望的输出状态却难以完整描述, 一般只通过某个 (或多个) 变量的值描述. 例如, 针对某个输出状态mO, 期望的函数的返回值为1, 可记为mO={(a0, 0x1)}. 显然, 不完整的机器状态描述为测试带来诸多隐患. 例如, 程序满足期望的输出值并通过测试, 但其间可能修改了预期之外的内存值或callee-saved寄存器值从而引发安全问题.
3.3 语义等价性测试模型对于两段程序p0和p1和任意的机器状态m, 严格的语义等价可描述为:
| ${p_0}(m) = {p_1}(m)$ |
该定义需对比任意输入状态下的完整输出机器状态以确保语义的等价, 相比一般测试模型具有更为严格的定义以确保捕获程序的副作用. 显然, 我们无法负担对任意机器状态的穷举. 另外, 完整地描述机器状态通常是没有必要的. 例如, 在第2节介绍的ABI中, RISC-V的32个整型寄存器中有16个属于调用者维护, 允许用户程序进行修改而无须恢复现场, 若两个待测程序对某些调用者维护的寄存器进行了不同的修改, 仍可认为其语义等价. 实际上, 在调用者维护的寄存器中, 除用于存放返回值的寄存器外, 大部分寄存器无须在测试中进行描述.
我们将语义等价性测试模型描述为三元组(P, M, K), 包括一组待测程序
| $\forall {p_x},{p_y} \in P,\;\forall m \in M,\;\forall k \in K,\;{p_x}(m)[k] = {p_y}(m)[k]$ |
与一般的测试模型不同的是, 语义等价性测试模型: (1) 规定了一组键作为测试标准, 通常包括返回值寄存器a0, 被调用者维护的寄存器、某些内存值等, 远远多于一般测试的某几个观测值; (2) 无须给定输入机器状态对应的输出机器状态, 即无须由用户为相应键k计算值v.
4 系统设计基于第3.3节介绍的语义等价性测试模型, 我们设计了面向RISC-V的汇编程序语义等价性自动化测试系统. 本节介绍总体框架(4.1节)以及其中的系统配置(4.2节)、测试运行(4.3节)和结果分析(4.4节) 3个环节.
4.1 总体框架测试系统的整体流程如图 2所示. 其中, 系统配置环节准备了测试所需的测试用例和一组待测程序, 并由用户配置测试目标. 之后, 系统分别运行各个待测程序并同时追踪机器的状态变化, 记录下在运行过程中被更改的机器状态. 最后, 通过比对各个待测程序更改的机器状态, 结合测试目标, 生成语义等价性测试的测试报告.
|
图 2 语义等价性测试系统整体流程图 |
4.2 系统配置 4.2.1 生成测试用例
测试用例的生成[13,14]与本系统相对独立, 可以采用手工编写或在给定约束下自动生成两种方法. 与传统的“输入-输出”模式的测试用例不同, 语义等价性测试并不要求用户给定期望的输出值, 只需要比对待测程序的运行结果是否一致即可, 这大大减少了生成测试用例的工作量. 本系统采用测试用例的自动生成, 以函数int add(int a, int b)为例, 在给定参数的数据类型int的前提下, 系统随机生成一系列测试用例, 如a=1, b=2; a=99, b=−99等.
4.2.2 准备待测程序为保持待测程序运行前机器状态的一致性, 系统分别对每个待测程序进行“汇编-链接”, 生成可执行文件 (见图 3) . 其中测试用例负责准备输入参数并调用相应的待测程序, 为提示模拟器待测程序运行的开始和结束, 系统在待测程序的开始和结束插入两条指示性的自定义指令test_start和test_end, 并同时在汇编器和模拟器中添加支持. 另一个可行的实现思路是: 通过保存模拟器的状态, 实现在同一状态下分别调用不同的待测程序.
|
图 3 待测程序生成可执行文件流程图 |
4.2.3 配置测试目标
用户的测试目标, 即第3.3节中的集合K, 在本系统中是可配置的, 覆盖寄存器及内存的值. 具体地, 用户需要配置: (1) 观测目标, 包括反映程序功能正确性的寄存器或内存的值 (如作为返回值的a0寄存器); (2) 约束条件, 包括是否允许待测程序修改被调用者维护的寄存器或其他内存值.
4.3 测试运行单个待测程序的测试运行流程如图 4所示. 系统基于RISC-V软件模拟器对输入的可执行文件进行译码和执行, 在识别自定义的test_start后, 记录初始的机器状态, 运行待测程序, 并同时跟踪机器状态的变化, 直至运行test_end后, 记录最终所有被更改的机器状态.
4.4 结果分析图 5给出了系统针对一组待测程序的测试运行和结果分析流程图. 系统通过将多个更改的机器状态进行比对, 结合用户配置的测试目标, 形成最终的测试报告. 若所有待测程序在观测目标上产生了相同的结果并满足其他约束条件, 则测试通过.
5 系统实现本系统基于Spike模拟器实现. 支持扩充的指示性指令 (test_start和test_end) 所需的汇编器基于LLVM[15]后端实现, 链接器使用RISC-V的gcc工具链 (C库使用newlib). 向量扩展指令的指令编码及Spike模拟器功能实现遵循RVV-0.9规范.
|
图 4 单个待测程序测试运行流程图 |
|
图 5 一组待测程序测试运行及结果分析流程图 |
系统利用伪随机数实现了支持常用数据类型的测试用例随机自动生成的函数库, 包括整型、浮点型、字符型、字符串型等. 用户通过提供参数类型, 取值范围等信息可自动生成随机的测试用例.
系统支持通过JSON文件配置测试目标 (示例见图 6). 其中, 决定程序正确性的观测目标可用户根据ABI和程序的具体功能手动设置, 默认观测目标为a0寄存器. 另外, 如图 6所示, 用户可直接配置是否允许修改调用者维护的寄存器和其他内存值.
|
图 6 测试目标配置文件config.json示例 |
系统在运行test_end指令时输出寄存器文件以对比寄存器值. 对于内存值, 系统采取在模拟器插桩的方式监测内存变化. 具体地, 在运行test_start指令后, 所有store类指令会额外记录目标内存地址, 并在执行test_end是输出记录的内存地址及内存值.
图 7展示了针对某个测试用例的测试报告模板, 分为测试结果、观测目标、内存及被调用者维护的寄存器和其他.
|
图 7 测试报告模板 |
6 实验与结果
本实验旨在验证语义等价性测试系统的有效性, 并以一般的测试系统为基准, 评估其测试效果和时间开销. 实验运行于Intel Core i7-9700 CPU以及32 GB内存的机器, 使用Ubuntu 20.04操作系统, 实验结果均为运行5次的平均值.
6.1 测试集构造我们选取5个常用C函数 (见表 1) 作为系统的测试集, 每个函数具有一个标准版本、一个基于RVV的向量版本以及两个变异版本. 为充分验证系统的测试有效性, 我们基于每个向量版本, 为程序引入副作用: (1) 将程序中某个被调用者维护的寄存器更改为调用者维护的寄存器形成变异版1; (2) 在程序中插入一条store指令更改某个指针参数对应的内存中的值形成变异版2. 表 1中, “9、11”表示memcpy的两个变异版本的代码量分别是9和11.
|
表 1 常用C函数组成的汇编程序测试集 |
6.2 系统有效性验证及时间开销评估
为验证本系统的有效性, 实验采取随机生成的1000个测试用例分别对 “标准-向量”“标准-变异1”和“标准-变异2”共3组程序进行语义等价性测试 (简称等价测试), 并同时运行一般测试 (仅比较函数观测目标) 作为对比.
表 2给出了测试结果和时间开销. 语义等价的 “标准&向量”组通过了一般测试及等价测试. 但面对具有副作用的两个变异版本, 一般测试依然显示通过, 而等价测试通过更加严格的机器状态对比, 有效地捕获到副作用, 并报告测试未通过.
|
|
表 2 基于1000个测试用例的一般测试和等价测试的有效性和时间对比 |
时间开销方面, 等价测试由于追踪、记录、对比机器状态而相比一般测试平均带来约350%的额外时间开销. 但由于等价测试通常针对函数级的程序, 时间开销通常是可接受的. 例如向量计算函数saxpy在1000个测试用例下仅用时0.14 s左右.
6.3 案例分析本节以函数strlen为例, 分析系统的测试有效性. 表 3给出了strlen的函数声明、某测试用例、正确的返回值以及测试目标. 该函数运行结束后, 由标准版函数计算观测得出, 观测目标a0应为0x20, 即整数32. 另外, 用户规定被调用者维护的寄存器和运行时栈以外的内存值在函数运行后不允许修改.
|
|
表 3 函数strlen的测试用例及测试目标 |
函数strlen的向量版本及相应的两个变异版本的生成方式见图 8. 其中, 变异版1修改了被调用者维护的寄存器, 而变异版2修改了内存值, 二者均不满足测试目标. 传统的基于返回值对比的测试方法因无 法捕获此类副作用而通过了测试. 基于语义等价性测试系统, 我们分别对“标准-向量”“标准-变异1”和“标准-变异2”这3组程序进行测试. 三者的测试报告见图 9. 其中, 正确的向量版函数产生了与标准版相同的观测值 (a0) , 并未引入任何违反测试目标的副作用, 成功通过测试. 变异版1修改了被调用者维护的寄存器s1, 变异版2修改了内存地址0x23f00的值, 均违反了测试目标而未通过测试.
|
图 8 函数strlen向量及变异版本 |
|
图 9 函数strlen的测试报告 |
此案例表明, 本系统能够通过跟踪机器状态, 结合测试目标, 有效地捕获程序产生的副作用, 提供严格有效的语义等价性测试.
7 总结与展望本研究基于Spike模拟器, 设计并实现一套面向RISC-V的汇编程序语义等价性自动化测试系统, 通过比对不同程序运行后的全机器状态 (寄存器、内存等) , 结合用户配置的测试目标, 自动完成测试并生成测试报告. 实验表明, 本系统可成功捕获程序运行的副作用, 为语义等价性有效地提供了更为严格的测试环境.
基于本系统, 未来可通过以下3方面继续提高语义等价性测试的有效性和易用性: (1) 结合模糊测试技术, 更为有效地生成测试用例, 提高测试的分支覆盖率和有效性; (2) 结合缺陷定位技术[16,17], 为语句进行可疑性排序, 提高系统的易用性; (3) 采用动静结合的方式[11]对汇编语义等价性进行更为严格的测试.
| [1] |
Pierce BC. Types and Programming Languages. Cambridge: The MIT Press, 2002.
|
| [2] |
Chaitin GJ. Register allocation & spilling via graph coloring. ACM SIGPLAN Notices, 1982, 17(6): 98-101. DOI:10.1145/872726.806984 |
| [3] |
张新华, 何永前. 软件测试方法概述. 科技视界, 2012(4): 35-37. |
| [4] |
单锦辉, 姜瑛, 孙萍. 软件测试研究进展. 北京大学学报(自然科学版), 2005, 41(1): 134-145. DOI:10.3321/j.issn:0479-8023.2005.01.020 |
| [5] |
Tse AY. Software testing apparatus and method. US, 5742754. (1998-04-21).
|
| [6] |
王戟, 詹乃军, 冯新宇, 等. 形式化方法概貌. 软件学报, 2019, 30(1): 33-61. DOI:10.13328/j.cnki.jos.005652 |
| [7] |
King JC. Symbolic execution and program testing. Commu-nications of the ACM, 1976, 19(7): 385-394. DOI:10.1145/360248.360252 |
| [8] |
Yan H, Sui Y, Chen SP, et al. Spatio-temporal context reduction: A pointer-analysis-based static approach for detecting use-after-free vulnerabilities. Proceedings of the 40th International Conference on Software Engineering. New York: ACM, 2018. 327–337.
|
| [9] |
Godefroid P, Levin M, Molnar D. Automated whitebox fuzz testing. Proceedings of Network and Distributed Systems Security. San Diego: Internet Society. 2011.
|
| [10] |
谢肖飞, 李晓红, 陈翔, 等. 基于符号执行与模糊测试的混合测试方法. 软件学报, 2019, 30(10): 3071-3089. DOI:10.13328/j.cnki.jos.005789 |
| [11] |
Lim JP, Nagarakatte S. Automatic equivalence checking for assembly implementations of cryptography libraries. 2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO). Washington DC: IEEE, 2019. 37–49.
|
| [12] |
Bellard F. QEMU, a fast and portable dynamic translator. Proceedings of the annual conference on USENIX Annual Technical Conference. Anaheim: USENIX Association, 2005. 41.
|
| [13] |
宋倩. 基于遗传算法的测试用例生成技术. 计算机系统应用, 2014, 23(11): 264-267. DOI:10.3969/j.issn.1003-3254.2014.11.050 |
| [14] |
Godefroid P, Klarlund N, Sen K. DART: Directed automated random testing. Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2005. 213–223.
|
| [15] |
Chris L and Vikram A. LLVM: A compilation framework for lifelong program analysis & transformation. International Symposium on Code Generation and Optimization, 2004. CGO 2004. San Jose: IEEE, 2004. 75–86.
|
| [16] |
陈翔, 鞠小林, 万志, 等. 基于程序频谱的动态缺陷定位方法研究. 软件学报, 2015, 26(2): 390-412. DOI:10.13328/j.cnki.jos.004708 |
| [17] |
Wong WE, Gao RZ, Li YH, et al. A survey on software fault localization. IEEE Transactions on Software Engineering, 2016, 42(8): 707-740. DOI:10.1109/TSE.2016.2521368 |