分享一篇来自USENIXSE' 23的文章,题目为:"AURC: Detecting Errors in Program Code and Documentation"。
长文警告!!!
程序代码和文档中的错误检测是计算机安全中的一个关键问题。先前的研究表明,通过广泛的代码或文档引导分析,有助于漏洞发现。然而,现有技术有以下重大限制:(1)它们假设文档是正确的,并将违反文档的代码视为bug,因此如果API的文档有缺陷或没有文档,则无法发现文档的缺陷和代码的bug;(2)它们利用多数表决来判断不一致的代码片段,并将异常代码视为bug,因此无法处理正确用法较少或所有用例都错误的情况。
Motivation
在Listing 1中,2-3行是OpenSSL对EVP_SealInit()
用法的描述,通过声明错误发生时返回零,文档指导开发人员进行返回值检查,并在调用EVP_SealInit()
时为返回的0错误处理代码。第17行显示了对EVP_SealInit()
的调用,其中openssl_seal
函数是调用者,而EVP_SealInit()
的源代码是被调用者。开发者可以参考被调用者、文档或其他调用者来学习API的用法,本文称之为API用法参考(API Usage References,AUR)。
然而,PHP解释器中的调用者和OpenSSL的文档都忽略了负值。被调用者与调用者和文档不一致,导致对PHP解释器的拒绝服务(DoS)攻击(CVE-2017-11144)。
先进的方法已经通过一致性检查发现了许多潜在的漏洞。然而,它们面临三个主要问题:(1)文档中仅覆盖了有限数量的API。一些方法通过从文档中提取用法并将其用作定位偏离代码的标准来检测潜在的错误。然而,许多API没有文档并因此避免了检测。更糟糕的是,即使文档本身可能包含缺陷。例如,作者发现的204个错误的被调用者没有文档,而 91 个错误的被调用者的文档有缺陷。(2)多数表决(Majority Voting)方式可能无法执行或不正确。一些研究对调用者进行了广泛的代码分析,并基于多数表决的方法检测潜在的错误,即最常见的用法是正确的。不幸的是,它仅适用于多次调用的API,而最常见的用法也可能是错误的。例如,作者发现的104个错误的被调用者调用次数太少,无法进行多数表决;而在311个错误的被调用者中,占主导地位的用法是错误的。(3)在上下文范围内可能不存在正确的用法。一些研究尝试基于相似的函数上下文检测错误。例如,它们在相同函数中使用相似的执行路径。然而,这需要在上下文中存在正确的用法。
作者观察到所有AURs都可以在上下文规模中隐式或显式地提供用法,而不仅仅利用先前研究中的文档和调用者。特别是被调用者,即使很少调用或未记录,这种现象也是存在的。因此,从所有AURs收集用法并通过在它们之间进行一致性交叉检查来推断正确性可以解决上述限制。然而,从AURs中提取用法并推断正确性存在以下挑战:
挑战一,复杂的数据流使得很难预测被调用者的使用情况。为了通过AURs之间的交叉检查来检测不正确的返回检查,就需要预测被调用者的返回值。错综复杂的数据流影响了这一预测。一方面,嵌套调用通常用于返回值赋值。例如,在预测OpenSSL中pkey_ec_ctrl_str()
的返回值时,必须查看至少53个函数来追踪其来源。另一方面,即使在函数内部,返回语句也出现在执行路径的尾部,这使得传统的分析技术(如值范围分析)在到达返回语句之前必须经过许多语句。此外,普遍存在的return
语句使本已繁重的分析更加繁重。例如,pkey_ec_ctrl_str()
仅包含32行代码,令人惊讶的是它拥有16条执行路径(忽略嵌套调用)和8条返回语句。
挑战二,文档和代码不能直接比较。文档是面向人的,用自然语言编写,而调用者和被调用者是代码。不能直接比较它们。因为需要对被调用者和调用者进行嵌入。在嵌入过程中,文档中变化无常的句子结构阻碍了与用法相关的句子的提取。先前的研究利用手动设计的模板来过滤句子。然而,它们是劳动密集型的,并且难以应对代码库迁移。此外,包含数字或范围的多变词汇降低了转换的准确性。例如,"BIO_seek() and BIO_tell() both return the current file position on success and -1 for failure"来自OpenSSL的文档。句子中存在暗示类似位置范围的描述性词语。人类可以看一眼就理解它们,但自动分析不能。
挑战三,当不一致发生时,确定有缺陷的是一个两难的问题。从所有AURs中提取用法后,在出现不一致时找到一种合理的方法来推断正确性至关重要。但是,文档、调用者和被调用者都可能有缺陷。假设一方是正确的、是直截了当的,但不可靠。一些研究定位这种不一致并手动执行正确性推断,但这很费力。此外,自动正确性推断至关重要,因为它是自动修补的基础。一些方法假设一个AUR(通常是文档)是正确的,而其他方法则假设最常见的用法是正确的。然而,这两种策略经常是不正确的,因为作者已经发现了许多违反它们的错误。
本文设计了一种AUR一致性检查方法AURC,旨在发现代码和文档中的潜在缺陷。AURC侧重于不正确的返回检查,从所有AURs中提取用法以检测不一致,并将发现的不一致发送到正确性推理模块以推断有缺陷的错误。
AURC的框架如图1所示,包括六个主要模块:上下文敏感回溯预测(Context-sensitive Backtrace Prediction,CBP)、截断点集(Cut-off Point Set,CoPS)构建、范围演绎树(Range Deduction Tree,RDT)、预训练分类器、映射表、正确性推理。具体来说,CBP分析被调用者,即API的源代码,并推断其返回值。CoPS从调用者收集返回检查,捕获if
语句的条件,并存储比较的操作数和符号。RDT根据CoPS中的条件推断返回值的范围。两个模块负责分析文档:预先训练的分类器过滤出与返回值相关的句子;映射表将它们转换为数字,以便进一步与被调用者和调用者的用法进行比较。在分析AUR之后(该过程可以并行执行),AURC执行交叉检查以定位不一致之处,并将它们发送到正确性推断,该推断包含四条规则以推断有缺陷的AUR。
图2展示了一个不正确的返回值检查示例代码。首先分析被调用者。BN_bn2binpad()
将参数a
的绝对值转换成big-endian类型并存储在to
中。AURC首先通过CBP推断BN_bn2binpad()
的返回值,即:-1
或bn2binpad()
。同样的,AURC推断bn2binpad()
的返回值包含-1
和>0
。最终,确定BN_bn2binpad()
的返回值为-1
和>0
。接着分析文档。通过微调的预训练的分类器挑选出用于描述BN_bn2binpad()
返回值的语句,即:the number of bytes和-1;其中,前者被映射为0。因此可知BN_bn2binpad()
的返回值是-1
和>0
。最后分析调用者。AURC收集if
语句的条件来分析调用者,并挑选出包含与被调用者返回值进行比较的条件来构建CoPS,如图2中的case 1-4所示。case 3使用了一个一元运算符!来进行返回值检查。因此,RDT判断BN_bn2binpad()
包含零和非零。这与分析的被调用者和文档结果不一致。因此,需要正确性推理模块介入。由于被调用者和文档的分析结果是一致的,因此认为库的开发人员工作是自洽的;所以认为调用者是有缺陷的。
下面详细介绍AURC的各个模块。
一、分析被调用者
CBP基于三点观察:(1)可以通过在调用者面前分析被调用的函数并用它们的返回值替换调用来将嵌套调用转换为过程内问题。(2)值域分析利用约束推导规则提取约束,以构建描述变量值域约束的约束图。类似地,作者总结了返回变量的三种路径约束,它们可以通过排除不合理的返回值来减少误报。(3)大多数返回值可以通过从返回语句回溯一些语句来预测,而不是从前到后分析整个函数。因此,CBP包含三个阶段:功能分析决策顺序、路径约束提取和回溯预测。
(1)功能分析决策顺序
CBP在调用者之前分析被调用的函数,用它们的返回值替换调用。这个阶段推导分析序列,以确保在调用者之前分析被调用的函数。具体来说,CBP构建全局调用图并删除调用图上拥有后边的节点,即:直接或间接调用自身的函数。然后,CBP计算调用图的拓扑排序以得到分析顺序。后面两个阶段按照这个顺序分析每个函数。
(2)路径约束提取
CBP通过遍历CFG生成函数的执行路径,并收集每个执行路径的路径约束。具体来说,在分析了大量代码后,作者总结了三种经常出现的路径约束:
if
语句约束条件。假设有一个if
语句if (cond) {statement1} else {statement2}
和一个返回变量R
的执行路径P
;还假设cond
包含变量R
。如果statement1
在P
中,那么R
应该满足条件cond
。否则,R
应该满足not cond
。用来表示R
应该满足的条件,即cond
或not cond
。对于包含n个if
语句的执行路径P
,约束被定义为:例如,在Listing 3中包含路径3,4,5,6,其中包含4和5两处if
条件句。为了到达6,4和5的return
语句都不能被执行。因此,recvd
应该满足recvd != 1
和recvd != 0
。这样一来CBP才能从当前执行路径中确定返回值不包括-1
和0
。
下标约束。CBP检测返回值R
是否来自于一个长度为S
的数组的下标。如果是,则约束定义为:
循环计数器约束。返回值也可能取决于循环的induction变量i
(我理解就是循环条件吧?)。AUCR尝试模拟i
的值来推断返回值。具体来说,作者观察到循环的induction变量收到初始值和退出条件的限制。因此,通过计算i
的值。其中函数用于计算两个参数的间隔。循环计数器条件定义为:
其中表示根据计算R
。例如,在Listing 3中用箭头标记的执行路径返回i
(第21行),这个值来源于循环中的induction变量。CBP推断该执行路径的返回值区间为.
(3)回溯预测
给定执行路径及其返回值约束,CBP需要预测返回值,如算法1所示。CBP首先获取执行路径的返回变量(第2行)并检查它是否是可预测对象(第4行)。可预测对象包含数字文字、表示0和1的逻辑表达式、其值可以从先前预测函数的返回值中推断出来的调用,以及源自上述对象的变量。可预测对象表示的值可以通过CBP直接获得(第5行)。如果返回的变量是不可预测的,CBP向后搜索到达定义,直到找到一个可预测的对象(第8行)。CBP排除了从路径约束提取中获得的约束值(第14行)。左边的值是执行路径的返回值。
例如,在Listing 3中,以ebcdic_gets()
为例。AURC首先提取它的执行路径。在预测返回值ret
时,关注箭头标记的路径。接着,AURC提取该执行路径的路径约束,即:14行(ret <= 0
)和21行(ret < 0
)的条件约束。进一步确定ret
的范围是<0
。接着,AURC迭代搜索ret
的定义点,并在第一轮迭代中确定该定义点在第13行。在这里,ret
被分配了一个可预测对象,即:ebcdic_read()
函数的返回值(预先分析确定返回值包含-2
、-1
、0
和>0
)。结合路径约束得出的结果,最终确定ebcdic_gets()
返回值为-2
和-1
。
二、分析调用者
返回值检查可以简介反映调用者对被调用者的理解。在Listing 4中,通过使用ret < 0
执行返回值检测,__get_cur_name_and_parent()
能够认为gen_unique_name()
的返回值包含两种类型,即:< 0
和>= 0
。
基于这一观察,AURC收集所有调用的返回值检查,并使用它们来构建CoPS。CoPS是包含if
语句条件的集合。通过分析条件中比较的符号和操作数,AURC可以从调用者的角度推断返回值的范围和被调用者的不同执行状态之间的对应关系。CoPS中的元素格式为(callee, symbol, value, location)
。callee、symbol、value
源自if
语句条件内的比较。它们记录被调用者、比较符号和比较操作数。location
记录检查的调用发生的位置,并在返回值检查有缺陷并被报告时提供位置信息。例如,AURC会将Listing 4的第6行转换成(gen_unique_name, <, 0, __get_cur_name_and_parent:5)
,并将之存储到CoPS。
然而,代码风格的多样性阻碍了CoPS的构建。在Listing 4中,调用者可以单独检查调用:第3行和第4行都检查第2行中的调用。如果AURC在推断范围时只考虑其中一项检查,假阳性将很高。因此,AURC基于数据依赖图(DDG)构建CoPS来解决上述问题,以确保捕获检查的完整性。具体来说,AURC遍历DDG包含调用的每个节点。如果节点包含类似if (gen_unique_name()<0)
的直接比较,AURC可以直接转换并保存在CoPS中。否则,如果节点将调用分配给另一个变量,AURC将进一步遍历依赖于该节点的每个节点,以收集与该变量相关的所有比较。调用和比较也将保存在CoPS中。这样,由于第3行和第4行都依赖于第2行,AURC可以在返回检查第2行中的is_inode_existent()
时收集它们。
单独的检查还会妨碍从返回值检查中推断返回值的范围。例如,第3行中的ret < 0
将返回值的范围分为< 0
和>= 0
,而第4行的!ret
将范围分为0
和!0
。由于这两项检查都检查了第2行中的调用,因此它们将返回值的范围分为< 0
、0
和> 0
。> 0
是一个隐式范围,因为它不能通过对调用的任何单次检查得出。捕获这个隐式范围的关键是要意识到到达第4行的前提条件是第3行中的条件,即:ret < 0
不满足,这意味着ret > = 0
。基于这一观察,作者提出了范围演绎树,简称RDT,以推断返回检查的返回值的范围。具体来说,对于调用的所有返回值检查,AURC首先基于CFG中这些检查的关系构建RDT。如果一个检查A是CFG中另一个检查B的父节点或祖先节点,则它们在RDT中保持相同的关系。此外,RDT的边标明了沿着这些边前进的先决条件。从RDT的根节点开始,AURC用边中的先决条件结束每一次检查,以推断最终范围。图3显示了一个由RDT推导第2行调用的返回值范围的示例。借助边的先决条件,AURC得出结论,范围包括< 0
、0
和> 0
。
三、分析文档
文档作为AUR的一种,以自然语言描述API的返回值。从文档中提取返回值进行比较并非易事,原因有两个:首先,文书缺乏严格的书写规范。与返回值相关的句子很难被过滤掉,因为它们与其他句子交织在一起。第二,与返回值相关的句子是面向人类的,包含人类可以轻松理解但不能用于自动比较的短语,如:return the number of characters written。
AURC采用了一种基于嵌入的方法来识别所需的句子。具体来说,AURC利用BERT进行分类,方法是使用包含文档句子的手动标记数据集对分类器进行了微调。
下表式AURC在文本预处理过程中用到的映射表。
四、缺陷预测
AURC所用的正确性推断规则如表3所示。
规则1:如果调用者与被调用者和文档不一致,则调用者有bug。从API开发人员的角度来看,他们的职责是开发被调用者并在文档中描述用法。如果文档和被调用者一致,那么不一致是因为调用者违反了调用被调用者时描述的文档用法。
规则2:如果文档与被调用者和调用者不一致,则文档存在缺陷。如果调用者和被调用者是一致的,那么代码将无缺陷地执行。此时,更新文档既不会影响现有代码,也不会留下未解决的不一致问题。此外,由于代码的快速发展,修复过时的文档是很常见的。
规则3:当文档不存在时,如果调用者与被调用者不一致,则调用者有bug。如果文档中不存在对被调用者的描述,则被调用者的源代码是提供用法的唯一可靠来源。因此,当不一致发生时,调用者应该跟随被调用者。
规则4:如果被调用者与文档不一致,并且调用者或所有AUR不一致,则需要进一步人工检查。
下面是一些实验结果。