目标符合性论证中成本优化的证据收集方法*

李 璇，吴 际，刘 超，杨海燕

北京航空航天大学 计算机学院，北京 100191

1 引言

证据定义为用于符合性论证的数据[1]，即论证过程的输入。证据收集成本用于描述将该证据“能证明目标满足符合性要求”的置信度从x提升到x+∆x所花费的绝对成本。其中，∆x理解为证据收集力度。

在实际案例中，证据信息主要通过申请者从大量文档、源文件和测试日志等收集获得。依赖人主观判断的证据收集通常是耗时和易出错的[2-3]，这主要归因于以下两方面：（1）收集者对目标的证据需求没有建立准确的认知，而收集大量无效的信息作为证据。（2）论证结构中复杂的论证关系和论证方法使得收集者难以判断证据效力，可能消耗大量成本在低效力证据收集上或在同效力证据项中错误选择了高收集成本的证据。

在避免收集无效证据的问题上，Panesar-Walawege等人提出了一种基于UML的模型驱动方法[4-5]以获得安全标准下所需要的证据；文献[6]提出了一种基于systematic literature review（SLR）的安全证据收集、组织和论证的方法。但对于如何从已知有效的证据集中确定下一步待收集的证据和收集力度，以保证高效低成本地完成目标符合性从不满足期望值到满足期望值的提升，尤其对采用定量评估方法的目标符合性论证来说，仍缺少有效的方法。

结合上述问题，本文的目标是结合目标符合性论证结构和过程信息，为证据收集者提供一种成本优化的证据收集方法，以保证目标符合性能够从不满足期望值提升到满足期望值。结合上述目标，本文基于动态规划[7]的思想，提出了一种基于成本分配模型的证据收集方案。考虑到论证方法中定量评估[8]较定性评估[9]引入了置信度的概念和复杂计算，以及定量评估中 BBN（Bayesian belief network）[10]和D-S证据理论[11]方法在数学层次上的关系，本文针对采用D-S证据理论和事件概率论证方法的目标符合性论证展开，更具有实际意义和拓展性。

本文第2章介绍了相关背景知识。第3章介绍了基于成本分配模型的证据收集方案的相关细节。第4章以案例的形式描述方案的实际应用过程，说明本文方案的有效性。第5章介绍了相关研究工作。第6章对本文工作进行总结并指出进一步的研究方向。

2 背景

2.1 论证模式

论证模式描述了证据对目标的向上论证关系，特别指出，子目标在用于论证父目标符合性时，被视为具有依赖的证据，这类证据不同于普通证据能够直接论证目标符合性，它们需要同其他子目标以“与”、“或”的方式来联合论证目标符合性。

在适航认证领域，目标或直接受普通证据论证，或至少存在两个子目标，存在子目标的目标不受普通证据直接论证，因为普通证据总能对应论证到该父目标的某一子目标项上。结合上述分析，论证结构主要包括4种基本论证模式，如图1所示。

Fig.1 4 basic demonstration modes图1 4种基本论证模式

其中，“单证据支持”表示目标符合性仅受单一普通证据论证，体现为1∶1的论证关系；“多证据支持”表示目标符合性受多条普通证据论证，体现为1∶n的论证关系；“与逻辑”定性描述为任意子目标符合性均满足是目标符合性满足的充要条件，体现为A&B→C的论证关系；“或逻辑”定性描述为存在子目标符合性满足是目标符合性满足的充要条件，体现为A|B→C的论证关系。文中将上述4种论证模式用一组统一描述规则定义如下：

其中，Object表示被论证的目标；ESet表示论证目标Object的证据集合；ArguType表示ESet对Object的向上论证关系，null表示ESet为普通证据集合，依据ESet中证据数量表现为单证据支持或多证据支持，and/or表示ESet为Object的子目标集，论证模式分别表现为“与逻辑”和“或逻辑”。

无法用上述4种论证模式直观表达的论证关系称为复杂论证模式。

2.2 D-S证据理论

D-S证据理论作为一种不确定推理方法，主要特点是：满足比贝叶斯概率论更弱的条件；具有直接表达“不确定”的能力。本文对于“单证据支持”和“多证据支持”论证模式采用了D-S证据理论论证上级目标的符合性，主要涉及的领域概念如下：

（1）识别框架Θ

对于识别框架Θ，总存在以下假设，就是在框架Θ中存在且仅存在一种可能性是该判决问题的答案，即在Θ中存在着唯一的真值。

（2）mass函数（也称为基本可信度分配）

（3）信度函数Bel

（4）m个mass函数的Dempster合成规则

对于∀A⊂Θ，识别框架Θ的有限个mass函数m1，m2,…,mn的Dempster合成规则为：

2.3 事件概率

对于相互独立事件A和B，A与B均发生A∩B的概率为P(AB)=P(A)×P(B)，A与B至少一件事件发生A∪B概率为P(A+B)=P(A)+P(B)-P(A)×P(B)=1-

本文对于“与逻辑”和“或逻辑”论证模式分别采用了交事件和合事件论证上级目标的符合性。

2.4 证据收集成本

依据工程经验可知，证据收集成本与置信度的相关性可描述为同类证据同样将置信度提升差值∆t时，起始基准较小的证据所花费的成本会低于另一项，即置信度v从0提升到0.3花费的成本必定小于/等于v从0.6到0.9花费的成本，甚至有可能随着起始基准的增加使得成本指数性增长。考虑到证据优化方案于提升证据置信度所花费的绝对成本，故而成本分布应依据证据置信度从当前值v提升∆t所需的绝对成本f(∆t,v)给出，实际使用中可借助Matlab等依据实际工程数据拟合获得成本分布函数。

3 基于成本分配模型的证据收集方案

成本分配模型描述了提升顶级父目标符合性到期望值时所花费的最低证据收集总成本及对应的证据收集方案。

其中，MinCost表示顶级父目标从HisValue提升到ReqValue花费的最小成本；TraceList表示最小成本下的证据收集链集合。

成本分配模型的构建过程涉及到两个模型、一项指南和3个规则。“两个模型”分别为目标符合性论证模型和目标符合性与成本关联模型，“一项指南”为原生复杂论证模式转换指南，“3个规则”为目标符合性提升范围划定规则、关联模型遍历规则和证据收集链构建规则。

目标符合性论证模型分别对适航领域存在的4种基本论证模式构建了对应的目标符合性论证公式，是目标符合性与成本关联模型构建要素之一。

目标符合性与成本关联模型定位于描述深度为2的论证结构下的顶级目标符合性成本关联关系，是成本分配模型实施过程的基本要素。

复杂论证模式转换指南能够保证上述两个面向4种基本论证模式的模型即使在复杂论证模式的情况下也能成功构建。

目标符合性提升范围划定规则用于为目标符合性与成本关联模型建立过程规避掉无效用的计算。

关联模型遍历规则描述了为论证结构中各目标建立关联模型时应遵循的构建顺序。

证据收集链构建规则描述了如何从顶级目标的关联模型中回溯获得最终的证据收集方案。

上述各模型与规则的作用关系如图2所示。

3.1 目标符合性论证模型

目标符合性论证模型的定义如下：

其中，CPSet为证据“能证明目标满足符合性要求”的置信度；ArguType为目标符合性论证方法。

当论证方法ArguType为D-S证据理论时，构建识别框架Θ={valid,unvalid,uncertain}，其中valid表示目标通过符合性认证这一断言成立的可信度，unvalid表示目标通过符合性认证这一断言不成立的可信度，uncertain表示不确定程度，则有：

Fig.2 Relationship between model and rule图2 模型与规则作用关系图

当论证方法ArguType为事件概率中的交事件时，目标通过符合性认证这一断言成立的充分条件是各证据项均通过符合性认证，则有：

当论证方法ArguType为事件概率中的合事件时，目标通过符合性认证这一断言成立的充分条件是存在证据项通过符合性认证，则有：

3.2 目标符合性与成本关联模型

关联模型以成本为目标函数，表示目标符合性程度每提升x所花费的证据收集成本。

其中，DP表示一种动态规划方案，是形成该关联模型的核心组件；HisValue表示目标符合性当前值；ReqValue表示目标符合性期望值；MinCost表示将目标符合性从HisValue提升到ReqValue的最小成本；ETuple表示收集成本为MinCost时的直接证据的收集方案，如下方式：

DP是以成本最低为目标的动态规划方案，其规划过程需要论证模式、论证方法、证据成本、目标符合性当前值和目标符合性期望值的支持。

其中，AM表示目标的论证模式；AU表示目标符合性论证函数；FSet表示证据成本集合；CPSet表示证据符合性程度当前值集合。

假设对目标g建立符合性与成本的关联模型，其中目标g符合性受n个证据e1,e2,…,en论证，每个证据的初始符合性程度记为ci,i=1,2,…,n,则DP动态规划方案执行步骤描述如下：

输入：AM，AU，Fset，CPSet，HistValue，ReqValue。

输出：C(g,k,k′)表示目标g符合性从k′提升到k所产生的最小成本；ETuple表示最小成本下的证据提升分配方案。

约束条件：

1.k=ReqValue,k′=HisValue

2.若AM.ArguType=null,n=1,即论证模式为“单证据支持”，则:

3.若AM.ArguType=null或AM.ArguType=and，即论证模式为“多证据支持”或“与逻辑”，则:

其中，Eg[k][i]表示最多提升目标g的前i个证据使得A符合性达到k的最低成本；pg(t1,t2,…,ti)表示目标g的前i个证据提升到ti所花费的成本。

4.若AM.ArguType=or即论证模式为“或逻辑”：

上述动态规划方案，依据论证模型作为优化过程中的约束条件，使得输出结果总能保证目标符合性达到期望值。该关联模型的建立，将论证结构中各目标符合性的提升成本从未知转为已知，使得后续成本分配模型得以展开。

3.3 复杂论证模式转换指南

目标符合性与成本关联模型应用场景建立在图1所描述的4种基本论证模式上。在论证结构中，可能会存在复杂论证模式，这类论证模式无法直接支持目标符合性与成本关联模型的建立。因此，本节给出一种转换指南指导复杂论证模式到基本论证模式的转换。转换的前提是保证论证结构转换前后的一致性，转换后论证模式应为4种基本论证模式的简单相加。

这里复杂论证模式指具有以下3种任意一种的表现形式：

（3）在同一目标→目标的论证维度下，无法用单一的“与逻辑”或“或逻辑”表示论证关系，表现为A&(B|C)→D或者A|(B&C)→D。

针对上述3种表现形式，建立转换指南如图3所示。

3.4 目标符合性提升范围划定规则

目标符合性提升范围Ug=[a,b]定义了顶级父目标符合性达到期望值时目标g自身符合性允许的取值区间。其中，a表示目标g的符合性至少要提升到a才使得顶级父目标符合性可能达到期望值，b表示目标g的符合性提升到b时使得顶级父目标符合性必定达到期望值。

通过为目标g设定提升范围，可以为后续目标符合性与成本关联模型建立过程规避掉无效用的计算，因为提升目标g的置信度到b肯定比b+ε的成本要低，而目标g的置信度小于a时获得的搜索组合无法使顶级目标置信度达到期望值。

Fig.3 Conversion guide图3 转换指南

目标符合性提升范围由父目标符合性的提升范围、目标符合性当前值及目标与父目标间的论证模式确定。依据上述要素，将影响性质划分为3类：

第一类目标：该类目标必使得顶级目标“通过符合性审查”的置信度小于期望值。

第二类目标：非第一类和第三类的目标。

第三类目标：该类目标必使得顶级目标“通过符合性审查”的置信度大于期望值。

设目标g的符合性当前取值为HV，其父目标r的提升范围为Up=[L,H]，则目标符合性提升范围Ug的划定规则如表1所示。

Table 1 Lifting rangeUg=[a,b]delineation rules表1 提升范围Ug=[a,b]划定规则

3.5 关联模型遍历规则

建立父目标的符合性与成本关联模型的前提是其1级子目标均建立了成本关联模型。在面向完整论证结构时，只有位于论证结构最底层的普通证据的成本分布是给定的，各级目标的成本均需要通过建立目标符合性与成本关联模型获得。

结合上述分析，将论证结构看作一棵论证树，其中顶级父目标为树的根节点，各级子目标按照论证层次作为树中的各级节点，普通证据为树的叶节点，定义关联模型遍历规则如下：

（1）后根遍历论证树的各目标子树。

（2）访问根节点，即顶级目标。

3.6 证据收集链构建规则

证据收集链是组成证据收集方案的基本单位，其具有以下性质：

（1）假设以父目标构建一棵树，则其证据收集链即为以链首为根节点的n棵子树，子树叶节点构成该链首项的证据收集集合，所有子树的叶节点构成该父目标的证据收集集合。

（2）证据收集链的总数表示了所需要提升的1级子目标数。

证据收集链的构建过程，即是基于广度遍历的关联模型搜索过程。定义证据收集链构建规则如下：

（1）初始化n条证据收集链，n表示顶级父目标关联模型下ETuple集中提升力度>0的项的总数，上述n项即为链首。

（2）建立一棵以顶级父目标为根节点的树，其子节点即为上述n项目标。

（3）广度遍历树，若节点为目标，则获得该目标关联模型下ETuple集中提升力度>0的m项，拓展为该节点的子节点；若节点为普通证据，不进行处理。

（4）当遍历结束时，证据提升链构建完成。

4 案例分析

为了说明方案的有效性，案例全覆盖了文中提到的各分支情况，包括4种基本论证模式、复杂论证模式、不同类别的目标，能够很好地诠释本文提出的方案在案例中的实施过程。案例分析的目标是说明方案的有效性：（1）方案能够覆盖标准符合性审查中的普遍论证模式；（2）依据方案能够获得满足约束条件的证据收集建议。

选取RTCA DO-178C[12]中的目标“High-level requirements comply with system requirements.”作为顶级目标，其对应的目标符合性论证结构如图4所示，数据信息如表2所示。

Fig.4 Argument structure图4 论证结构关系图

Table 2 Basic data information表2 基本数据信息表

A:High-level requirements comply with system requirements.

o1:All system requirements are satisfied by the high level requirements.

o2:Derived requirements and the reason for their existence are correctly defined.

o3:There is no derived requirements at all.

e1:Software verification results about the functional requirements compliance.

e2:Software verification results about the performance requirements compliance.

e3:Software verification results about the safety-related requirements compliance.

e4:Software verification results about the derived requirements compliance.

e5:Software verification results about the derived requirements recorded.

e6:Software verification results about the derived requirements recorded.

其中证据e1、e2、e3、e4到目标o1表现为多证据支持论证模式；证据e5到目标o2表现为单证据支持论证模式；证据e6到目标o3表现为单证据支持论证模式；目标o1、o2、o3到目标A表现为复杂论证模式。

其中，证据置信度与证据成本分布由申请人或专家提供，目标置信度通过上文中的目标符合性论证模型获得。在这里，本文问题重心定位为“目标符合性论证中成本优化的证据收集方法”,故前提条件中的证据置信度和证据成本分布均为仿真数据，真实数据由申请人或专家提供。

通过建立目标符合性与成本关联模型，获得目标o1、o2和o3的目标符合性与最小成本的对应关系如图5所示，其中x轴表示目标符合性取值，y轴表示最小成本，(x,y)表示将目标符合性从当前值提升到x所需的最小成本，数据标注描述了最小成本下的证据收集方案ETuple。

最后，对顶级父目标A建立关联模型，获得目标A符合性从0.89提升到0.94的最小成本为19.67，对应的直接收集方案为：提升目标o1符合性到0.97，提升目标o2符合性到0.95，提升目标o3符合性到0.40。依据证据收集链构建规则，获得最终的证据收集方案为表3所示。

Fig.5 Relationship between object conformance and minimum cost图5 目标符合性与最小成本对应关系图

Table 3 Evidence collection表3 证据收集方案

在实际收集过程中，可围绕提高证据的完备率或证据可信度展开。其中，证据的完备率表明了其支持目标通过符合性审查的能力，而证据收集方式的差异将会影响证据的可信度。举例来说，支持软件版本质量满足目标“最新版本的测试失效数大于5”的要求的证据是”最新版本的测试失效数为2”，假设该证据的置信度（0.7,0.1,0.2），若要提升置信度到（0.9,0,0.1），则可以考虑从（1）测试覆盖率；（2）RTOS4A复杂度；（3）测试成本；（4）测试方法等方面加以提升。

案例中覆盖了“基于证据的目标符合性评审”中会涉及到的4种论证模式，能够适用于符合性论证中的大多论证结构。同时，针对复杂的论证模式，给出了转换指南以指导完成复杂论证模式到基本论证模式的转换。说明目标符合性提升方案能够适用于多种论证场景。

将案例返回的证据优化方案作为验证信息，代入e1=(0.68,0.30,0.02)，e2=(0.50,0.20,0.30)，e3=(0.50,0.20,0.30)，e5=(0.70,0.10,0.20)，e6=(0.40,0.60,0)到目标A的符合性论证中获得A(0.941,0.052,0.007)，由于0.941>0.940，说明目标符合性提升方案能够保证目标A的符合性达到期望值0.940。

为验证证据收集方案划定的证据项是否满足高效低成本的要求，对目标o1的证据e1、e2、e3、e4在收集力度∆t=0.08下的效力和成本进行分析，得到表4。

Table 4 Effectiveness of evidence and cost under the same collection effort表4 同收集力度下的证据效力和成本

依据表4可知，在同等收集力度，证据e1不仅效力不低于其他证据，且成本最低，说明了证据收集方案结果的合理性。

依据案例中提供的各证据绝对成本分布函数绘制成本分布趋势如图6所示。

Fig.6 Evidence cost distribution图6 证据成本分布图

依据表3中的证据收集方案，观察图6可知，各证据的收集力度∆t均控制在绝对成本f(∆t,v)呈较低成本阶段，说明本文提出的以最低成本为目标提升方案是有效的。

5 相关工作

虽然目前存在与证据收集相关的研究和方法，但主要集中在如何避免收集无效证据和如何简化人工证据收集过程。

OMG（Object Management Group）在 2008年提出的SVBR（semantic business vocabulary and rules）[13]和在2011年提出的SACM（structured assurance case model）[14]，前者主要解决安全目标描述时自然语言表达的不一致性和二义性来描述安全目标,后者主要帮助构建和管理证据，但两者均缺少对证据收集过程的描述。

文献[5]提出了一种基于SLRs的安全证据收集、管理与评估的方法，但并未展开如何合理地组织证据来提高论证过程的相关研究。文献[15-16]设计了用于证据收集的工具。

基于上述相关研究，能够有效地帮助收集者收集与目标符合论证相关的有效证据，但忽略了有效证据间也存在论证效力和收集成本的差异。

本文从证据论证效力和收集成本出发，提出了一种新的证据收集角度来提升目标符合性论证结果，解决当前证据收集研究领域的局限性。

6 结束语

本文针对D-S证据理论和事件概率的目标符合性论证，提出了一种基于成本分配模型的证据收集方案，指导提升目标符合性到期望值的过程，以保证证据收集的成本较低。分析目标符合性论证结构，针对4种基本论证模式建立目标符合性关联模型，并为复杂论证模式建立转换指南以拓宽模型的适用性。在关联模型建立阶段，约束了目标符合性取值范围，有效地规避了无效用计算。在以后的研究中，将在关联模型的目标遍历规则中依据划分的目标类别构造遍历优先级，来代替当前平等的后根遍历算法以提高计算效率。此外，针对BNNs条件概率和主观逻辑与本文方案采用论证方法具有相通性，可拓展方案到适用于上述两种论证方法中。