基于多日志分析的大数据世系生成可行性证明

Theoretical Feasibility Proof of the Multi-Log Analysis-Based Big Data Provenance Generation Method

摘要

数据世系是实现大数据安全监管的有效方法。在大数据系统中，仅基于多日志分析的世系生成方法具有展现数据全生命周期完整世系视图的能力。但由于世系类型多样，该方法能否完整获取监管所需数据，即方法的理论可行性有待证明。为此，本文首次提出了一种形式化的证明方法。首先，对世系完整性进行了形式化定义。然后，通过对各日志包含的记录类型进行归约与关联，证明基于现有日志能否完整获取指定的世系信息；其中，提出了两种基于日志公共元素与基于程序运行原理的日志关联方法，用于对属性元素分散在多个日志中的世系类型的证明。最后，采用所提方法，证明了多日志分析方法能够用于Hadoop世系生成。

Abstract

Data provenance is a practical approach for data security supervision. In the big data system, only the provenance generation method based on multi-log analysis can present a complete provenance view of the data’s whole life cycle. However， due to the diversity of provenance types, the theoretical feasibility must be proved to determine whether the required provenance information for data supervision can be obtained entirely via this method. As such, this paper proposed a formal proof method for the first time. Firstly, the formal definition of provenance completeness was presented. Then, it is proven whether the specified provenance information can be fully obtained based on existing logs by reducing and associating the record types of each log. For the proof of provenance types whose attribute elements are spread out in multiple logs, two log association methods were suggested. These methods are based on common log elements and program operation principles. Finally, by adopting the proposed method, the multi-log analysis-based method proved feasible for Hadoop provenance generation.

Graphical abstract

关键词

大数据 / 世系数据生成 / 多日志分析 / 世系完整性证明 / Hadoop / Progger

Key words

big data / provenance data generation / multi-log analysis / provenance completeness proof / Hadoop / Progger

0　 引 言

当前，随着大数据应用领域的不断扩展，大数据安全事件也频频发生，数据安全监管和数据治理面临严峻挑战。

数据世系描述了数据的起源以及数据到达当前状态经历的操作与处理过程。精准掌握数据世系对于数据安全监管与数据治理至关重要^[1，2]。然而，大数据系统并不具备世系生成功能。世系数据需要由专门的方法追踪、生成。大数据系统通常采用分布式架构，支持海量用户访问，致使系统中的数据操作与处理过程复杂多样，获取能够支持对数据全生命周期进行监管的世系信息面临巨大挑战。

当前，世系生成方法包括操作系统（operating system, OS）级方法、应用级方法以及二者相结合的混合类方法^[3，4]。其中，仅混合类方法通过综合分析多种系统调用日志与应用日志生成世系数据^[3，5]，兼具前者信息丰富、后者语义丰富的优势^[6]，具备呈现数据对象全生命周期完整世系视图的能力。

基于多日志分析的混合类方法的可行性面临以下两个问题。首先，能够生成的世系信息取决于日志包含的信息；若日志不包含所需数据，那么该方法不可行。其次，很多世系类型的信息要从不同日志中提取，异构日志相关记录的关联是一个难题^[7，8]。为此，在构建多日志分析方法前，需要采用严谨的方法与过程证明此类方法的理论可行性，而不是仅凭直观判断认为可行；否则，生成的世系信息可能无法发挥世系的预期效用^[9]。在大数据场景中，由于数据的操作与处理过程复杂，导致世系类型多样、世系生成涉及的日志种类多并且相互间语义差异较大。证明该类方法能够完整获得所需世系信息是一个非常复杂的问题。当前，学术界对该问题的研究还是一个空白。

针对上述问题，本文把多日志分析方法的可行性定义为能够从日志中完整获取指定的世系信息。首先，对世系完整性进行了形式化定义。其次，提出了对各日志包含的记录类型进行归约与关联的方法，用于世系完整性的证明；其中，针对所含元素分散在多个日志中的世系类型，提出了两种基于日志公共元素与基于程序运行原理的日志关联方法，用于异构日志相关记录的关联与融合。最后，针对基于Hadoop的大数据系统，利用23种Hadoop日志和OS级世系追踪工具Progger^[10]日志的归约与关联结果，证明了采用多日志分析方法建立Hadoop数据世系是可行的。

1　 相关工作

1.1　数据世系与世系模型

数据世系翻译自“data provenance”一词。国内一些研究人员也将其译为“数据溯源”^[11]或“数据起源”^[12]。数据世系最早提出于数据库系统，用于描述源数据到查询结果的派生与演化过程^[13]，而后逐渐扩展到工作流系统、文件系统等应用领域。在不同的研究场景中，数据世系的涵义有所不同。数据监管不仅关注数据的创建、更新与销毁等动态变化，还关注数据的访问与使用行为，面向监管的数据世系涵盖了数据管理与处理系统支持的能够对数据造成访问事实的任意操作。

世系数据可看作一个有向无环图。世系模型定义了各类世系节点包含的属性元素与不同节点类型间的世系关系，是世系研究的基础^[14]。当前应用最广泛的是由万维网联盟世系工作组提出的世系数据模型（provenance data model, PROV-DM）^[15]。PROV-DM模型是高度抽象的。Gao等^[16]针对大数据场景对其进行改进，构建了一种面向监管的大数据世系模型（big data provenance model, BDPM）。BDPM模型包含三类顶级节点和十五类世系关系，如图1所示。在三类顶级节点中，实体（Entity）指数字对象，也即世系描述的对象；活动（Activity）作用于实体之上，引起实体状态的变化；代理（Agent）表示数据所有者与操作执行者。世系关系表达了三类节点间的世系关联。BDPM模型涵盖了大数据系统主要的数据类型以及数据存储与处理模式，能够有效表达数据对象生命周期内经历的各类活动。并且相比PROV-DM模型，BDPM模型新增了包含关系与共存关系以支持多粒度、多层级数据对象的监管。此外，实体间的包含/共存关系、实体与代理之间的归属关系可能会被活动改变。后文以“关系1”和“关系2”指代过去关系与当前关系，例如Inclusion1与Inclusion2分别对应图1中的wasIncludedBy与isIncludedBy。

本文参照在BDPM模型基础上建立的世系本体^[17]指定所需获取的世系信息。

1.2　基于多日志分析的世系生成方法

对于该类世系生成方法，异构日志的关联与融合是一个难题。Rupprecht等^[18]针对修改软件的世系生成方法时间开销较大的问题，提出利用日志等软件自然生成的数据与系统调用信息生成世系数据，但没有提出各类世系信息的关联方法。Ghoshal等^[7]提出了一种基于多日志分析的世系生成基础框架，分析了多日志关联面临的挑战，但未提出有效的解决方法。Datta等^[19]提出一种通过记录OS级与应用级世系信息生成应用行为完整视图的框架，未提出专门的多日志关联分析方法。Pasquier等^[5]在OS级与应用级世系信息的融合上，仅提出将应用日志存储在特定路径以进行融合，但未提出融合方法。Hassan等^[3]则针对两个层级信息融合的难题，利用应用日志写入进程即为文件操作执行进程的原理，将操作执行进程对应的OS级信息与日志写入进程对应的应用日志信息关联起来，但该原理并不适用于分布式大数据系统。Yu等^[6]针对多日志信息的融合，提出首先对各类日志进行标准化处理，而后基于日志记录的相同字段对不同日志的信息进行融合；然而，该方法对各应用日志的融合都是以底层审计日志为媒介，由于大数据系统在数据组织上的多层级性，将上层应用行为与底层进程行为一一对应是很难实现的。

综上，基于多日志分析的世系生成研究还处于起步阶段。在分布式、多应用大数据场景下，联合多种日志能否完整获取所需世系信息，也即该类方法的可行性缺乏证明。

1.3　Hadoop

Hadoop是由Apache开发的一种开源的、为满足数十亿网页数据的存储和计算需求而设计的分布式存储与计算框架。Hadoop拥有低部署成本、可扩展、高吞吐量、高容错等优势，已成为当前最主流的分布式大数据处理框架之一，在人工智能、科学计算等领域应用广泛^[20]。

Hadoop核心组件包括Hadoop分布式文件系统（Hadoop distributed file system， HDFS）、资源管理系统（yet another resource negotiator, YARN）与分布式数据处理引擎MapReduce。Hadoop对存储和计算资源的管理采用一种主从式架构。HDFS包含一个NameNode与多个DataNode。NameNode管理HDFS命名空间，DataNode存储文件数据。包含一个ResourceManager与多个NodeManager。前者负责整个集群的资源调度。后者则管理单个节点的资源，并负责启动与管理Container。Container是计算节点上的资源分配单元，具有作业管理与Map/Reduce任务执行功能。

2　 世系完整性证明方法

2.1　完整性的形式化定义

给定有限世系类型集合S_P 与日志集合S_L。S_P 中元素P表示为，“[]”中为可选属性。以I(P)表示P在有限条件集合C(P)下产生的实例集合，I(P)中元素I_P 表示P在特定条件下产生的一种实例；以A()表示属性集合。若\exists L\in S_L或能够从S_L 中构造日志L*（L与L*的记录类型集合分别以S_R 与S_R^{\mathrm{*}}表示），使得\forall P\in S_P且\forall I_P\in I(P)，\exists R\in S_R满足A(P)\subseteq A(R)且A(I_P)\subseteq A(R\mathit{实例})，或\exists R^{\mathrm{*}}\in S_R^{\mathrm{*}}满足A(P)\subseteq A(R^{\mathrm{*}})且A(I_P)\subseteq A(R^{\mathrm{*}}\mathrm{实例})，则称S_L 满足S_P 条件下的世系完整性。

根据上述定义，要满足世系完整性，有以下两个条件：

条件1：理论上，能够找到R或构造出R*包含P；

条件2：实际上，R或R*实例包含I_P。

条件1表示为集合之间的包含关系是由于很多世系类型的属性信息分散在不同记录类型中。例如P₁的属性attr₁与attr₂可分别从日志L₁与L₂的记录类型R₁与R₂中获得，若R₁与R₂无法通过某种方式建立关联（如公共元素，本文将在完整性证明过程中说明记录类型的关联方法），则R₁与R₂的实例必然无法对应起来，P₁的属性信息也就无法在世系生成过程中被完整获得。据此，世系完整性要求世系类型这一属性集合作为一个整体被完整生成。

条件2的设立一方面是由于记录类型R₁与R₂能够建立关联并不意味着R₁与R₂实例能够对应起来。例如，活动a₁产生了P₁与R₁实例，R₂实例由其他活动产生，那么从R₂实例中无法获得a₁相关的世系信息。因此，必须找到实例相关的R₁与R₂才能完整获得P₁信息。另一方面是由于大数据系统的数据操作与处理方式复杂多样，能够在C(P₁)限定的各类条件下从日志中完整获得I(P₁)信息，才能满足世系完整性。

从日志的角度看，能够满足上述条件的只有两种情况：一是某单一日志满足世系完整性，二是多种日志中记录类型的并集满足世系完整性。其中，并集的建立就是记录类型的构造。

2.2　完整性证明过程

已知条件：世系类型集合S_P，S_P 元素数量m。日志集合S_L，日志数量n。世系类型P的产生条件集合C(P)及实例集合I(P)。

前提条件：S_L 中的日志均处于开启状态，正常记录数据。

Step 1：日志归约

日志信息并非全部用于生成世系数据，并且各日志的语义差异较大，给世系完整性的证明带来干扰。例如在Hadoop日志中，同是表达文件操作对象的路径，HDFS审计日志（HDFS audit log，HA-Log）的相关字段为“src”与“dst”，HDFS事务日志EditLog的字段为“PATH”，Jetty NameNode日志（Jetty NameNode log，JNN-Log）则不包含专门字段，仅是将操作对象嵌入在记录中。

为便于世系类型属性与日志记录属性的对应以及各日志相关记录的关联，首先按照世系属性的语义，采用<世系类型：世系属性>的二元组形式对各日志记录的属性信息进行归约，使得针对特定的世系类型，不同记录类型在语义上保持一致。与世系信息无关的日志属性保持不变。

Step 2：证明是否\exists L\in S_L满足世系完整性定义

完全归纳法通过判断一类事物的每一个对象是否具有某种属性，最终判断整类事物是否具有该属性。运用完全归纳法逐一分析每一待证明对象的思想，依据日志归约结果，针对满足世系完整性的第一种情况，是否\exists L_k\in S_L(\mathrm{1}\le k\le n)，使得\forall P\in S_P，\exists R\in S_{R-L_k}，满足A(P)\subseteq A(R)，且\forall I_P\in I(P)，A(I_P)\subseteq A（R实例）。若存在，L_k 满足S_P 条件下的世系完整性，证明结束。否则，执行Step 3。

Step 3：证明能否构造L*满足世系完整性定义

Step 3分为两小步。首先证明在限定的世系实例产生条件下，各世系实例的任意属性是否都能从现有日志记录中获得。若能，选择可获得世系实例信息的记录类型进行日志构造。

Step 3-1：运用完全归纳法证明\forall I_{P_i}\in I(P_i)(\mathrm{1}\le i\le m)且\forall a\in A(I_{P_i})，\exists R\in S_{R-L_k}(L_k\in S_L)，使得a\in A（R实例）。若能够证明，从S_L 中选择出能够完整获得各世系实例属性信息的日志子集S_L^{\mathrm{*}}，执行Step 3-2，否则证明失败。

Step 3-2：令S_P^{\mathrm{*}}\in S_P，表示A(P)信息需要从多种记录中提取的世系类型集合，S_P^{\mathrm{*}}元素数量为q。采用完全归纳法证明能否基于S_L^{\mathrm{*}}构造日志L*，使得\forall P\in S_P^{\mathrm{*}}且\forall I_P\in I(P)，\exists R^{\mathrm{*}}\in S_R^{\mathrm{*}}，满足A(I_P)\subseteq A(R^*实例）。若能够证明，则L*满足S_R^{\mathrm{*}}条件下的世系完整性。

本文提出两种日志构造方法，也即相关日志记录类型的关联方法。不失一般性，假设A(P_{\mathrm{1}})\subseteq A(R_{\mathrm{1}})\bigcup A(R_{\mathrm{2}})。

第一种方法以不同记录类型的公有属性为连接点构造新的日志记录类型。对于这些记录类型的实例，则可以通过公有属性的相同值实现正确关联。本方法适用于以下两种情况：

1） R₁与R₂具有相同属性，如图2（a）所示。基于两者的公有属性能够构造R_{\mathrm{1}}^{\mathrm{*}}=R_{\mathrm{1}}\bigcup R_{\mathrm{2}}，满足A(P_{\mathrm{1}})\subseteq A(R_{\mathrm{1}}^{\mathrm{*}})。

2） R₁与R₂不具有相同属性，如图2（b）所示。若能够找到另一种记录类型R₃分别与R₁与R₂包含相同属性，能够以R₃为媒介构造R_{\mathrm{1}}^{\mathrm{*}}=R_{\mathrm{1}}\bigcup R_{\mathrm{2}}\bigcup R_{\mathrm{3}}，满足A(P_{\mathrm{1}})\subseteq A(R_{\mathrm{1}}^{\mathrm{*}})。媒介记录类型可能有多个，如图2（c）。

若基于公有属性的关联方法失效，则采用另一种基于程序运行原理的方法。在应用运行过程中，若任意R₁实例的产生必然伴随着R₂实例的产生（或反之），两实例具有一一对应关系，可基于它们的逻辑关联构造R_{\mathrm{1}}^{\mathrm{*}}=R_{\mathrm{1}}\bigcup R_{\mathrm{2}}，满足A(P_{\mathrm{1}})\subseteq A(R_{\mathrm{1}}^{\mathrm{*}})。

\forall P_i\in S_P^{\mathrm{*}}(\mathrm{1}\le i\le q)且\forall I_{P_i}\in I(P_i)，以S_{L-i}^{\mathrm{*}}表示包含A(P_i )信息的日志集合。采用上述方法，若能利用S_{L-i}^{\mathrm{*}}构造R_i^{\mathrm{*}}，满足A(I_{P_i})\subseteq A(R_i^{\mathrm{*}}\mathrm{实例})，最终能够证明S_L 满足S_P 条件下的世系完整性。

3　 基于多日志分析的Hadoop世系生成可行性证明

本节针对Hadoop这一具体对象，采用第2节所提方法，给定有限世系类型集合，并通过对23种Hadoop日志与Progger日志进行归约与关联，证明基于多日志分析的Hadoop世系生成可行性。

3.1　世系信息指定

本节参照BDPM本体，结合Hadoop数据监管需求，给定所需获取的有限世系类型集合。

3.1.1　世系节点

（1） 实体

HDFS是Hadoop的数据存储基础。HDFS文件是本文世系构建的核心。它在BDPM本体中的实体类型为HDFSFile，包含子类型HFile和HDirectory。HFile数据存储在以其数据块ID号命名的宿主机本地文件（简称块文件）中。块文件世系的建立能够促进对HFile使用行为的监管。本文选择的本地文件系统是第四代扩展文件系统（fourth extended file system， Ext4）。块文件实体类型为E4File。除用户外，HDFSFile还会被数据处理引擎处理。本文以MapReduce为例证明基于日志能够辨别并监管由软件代理执行的操作。所需实体类型还包括Job和Task。综上，指定的实体类型如下：

HFile:<ID, fileType, name, filePath, replication, t_c, t_a, t_m, t_d, permission, size, [xAttr₁,xAttr₂,…]>

HDirectory:<ID, fileType, name, filePath, t_c, t_a, t_m, t_d, permission, [xAttr₁,xAttr₂,…]>

E4File:<ID, size>

Job:<ID, jobType, name, inputs, outputs, t_s, t_e, finalStatus>

Task:<ID, taskType, t_s, t_e, finalStatus>

其中，ID表示世系节点标识符。对于实体，标识符可采用Hadoop设定的值，例如HDFSFile标识符是HDFS为其分配的唯一标识符inode ID。replication表示备份数量。t_c、t_a、t_m与t_d指创建、最近访问、最近修改与删除时间。[xAttr₁,xAttr₂,…]表示扩展属性集合。t_s与t_e表示开始与结束时间。finalStatus表示最终状态。

（2） 活动

根据指定的实体类型，所需活动类型如下：

FileDataOperation:<ID, [IP], [t_s, t_e, t_o], [arg₁,arg₂,…], [finalStatus], [mode]>

FileBasedAnalysis:<ID, t_s, t_e,finalStatus>

JobActivity:<ID, [IP]>

活动没有明确的标识信息，需要自行生成。FileDataOperation包括HDFSFile与E4File操作。t_o表示活动发生时间；[arg₁,arg₂,…]表示活动参数；mode表示操作执行模式，代表了用户访问HDFS的方式，共有命令行接口（command line interface, CLI）、WebHDFS、HttpFS和网络文件系统（network file system, NFS）四种；其中，NFS模式是把HDFS挂载到宿主机本地文件系统。

FileBasedAnalysis表示基于文件数据的分析活动，如MapReduce数据分析。

JobActivity包括三类子活动JobSubmission、TaskAssignment和TaskExecution。

（3） 代理

所需代理类型包括用户User，以及软件代理作业管理者JobMaster与任务工作者TaskWorker。对于MapReduce等分布式数据处理引擎，为充分利用集群计算资源，一个数据处理作业会被切分为多个任务，以并行方式执行。作业管理者执行任务创建，任务工作者执行数据处理。具体如下：

User:<ID>

JobMaster/TaskWorker:<ID, IP, t_s, t_e, finalStatus>

HDFS支持四种操作执行模式，用户能够使用任意模式，而软件代理在正常情况下仅采用CLI模式，这意味着相关世系信息（如HDFSFile操作信息）有五种生成条件。

3.1.2　世系关系

根据上述节点类型和BDPM模型定义的世系关系类型^[16]，所需关系类型包括：

Derivation:<e₁, e₂>

Coexistence1/Coexistence2/Inclusion1/Inclusion2:<e₁, e₂, [t_s,t_e]>

Usage:<a₁, e₁, [role], [t_s,t_e,t_o]>

Generation/Invalidation:<e₁, a₁>

Communication:<a₁, a₂>

Association:<a₁, ag₁>

Attribution1/Attribution2:<e₁, ag₁, t_s, [t_e]>

Delegation:<ag₁, ag₂, [a₁]>

在上述世系关系的表示形式中，前两个属性为被影响者与影响者的标识符，以此表明世系关系连接的节点。其中，e表示实体，a表示活动，ag表示代理。若两节点间可能存在多个同类型的世系关系，则通过时间信息或其他节点标识符进行唯一标识。例如，共存、包含与归属关系记录开始与结束时间。对于委托关系，两个代理间可能进行过多次委托，利用受托活动的标识符进行唯一标识。此外，对于使用关系，若一个活动使用了多个实体，在各使用关系中分别记录时间信息，若这些实体具有不同功能，记录角色信息进行区分。

3.2　可行性证明

3.2.1　Hadoop日志与Progger日志归约结果

按照指定的世系类型，本文采用Apache Hadoop 2.10.1，在各日志均正常记录的条件下，首先对23类Hadoop应用日志进行了调查与归约，即证明过程的Step 1。

各日志的归约结果如表1所示。在第二列中，序号1至12对应的日志属于HDFS日志，序号12至22对

应的日志属于日志，序号23对应的日志属于MapReduce日志；第三列为各日志记录的主要内容；第四列则表示各日志包含的本文指定的世系信息。下面对表中部分内容进行简要说明：

1） E4File标识符是HDFS为数据块分配的ID。Job标识符是为作业分配的ID。Task标识符采用“任务ID+作业尝试ID”的形式以确保唯一性。作业尝试表示作业的一次执行实例。允许一个作业在成功前尝试多次，并为不同的作业尝试分配相同的任务ID。用户标识符为用户名。

2） 仅当HDFSFile操作采用NFS模式执行时，HA-Log通过inode ID表示操作对象，其他模式下采用文件路径。

3） E4File操作的世系信息仅用于表达HFile操作的结果，不记录属性信息。

4） 在JobActivity的三类子活动中，仅JobSubmission需要记录作业提交的IP地址属性。

5） Container日志包括运行作业管理者的Container日志（application master container log, AC-Log）、Map Container日志和Reduce Container日志。

6） 作业历史文件、ResourceManager日志与AC-Log以主机名（host name）表示活动发生节点。本文Hadoop宿主机采用CentOS 6.5，可利用“/etc/hosts”文件将主机名归约为IP。

7） 当MapReduce作业被人为终止时，作业历史文件与AC-Log等记录作业执行过程的日志也即刻停止记录。此时将作业摘要日志（application summary log, AS-Log）中的作业结束时间作为相关任务与Container的结束时间。

8） 各世系关系的节点ID属性可从对应世系节点的属性信息中获得，不再列出其日志来源。

根据表1结果，首先执行Step 2，证明是否存在单一日志满足世系完整性。显然，没有任何一种日志满足条件1，证明失败，需要执行Step 3，日志构造。

执行Step 3-1，证明各世系类型实例的任意属性是否都能从上述Hadoop日志中获得，结果依然是否定的。第一，Hadoop未记录由HFile读取引起的块文件操作，无法准确得知HFile被实际读取的数据块，导致无法生成E4File操作的世系节点和相关的使用关系。第二，因为NFS网关的缓存功能，当某些操作采用NFS模式执行时，Hadoop可能不记录或记录不准确，如HDFSFile读取、移出挂载路径等。第三，HDFS日志将操作执行者全部记录为用户，而和MapReduce日志不记录Container执行的文件操作。若HDFSFile操作由软件代理执行，无法获得关联关系中的影响者标识符。

截获系统调用并提取OS级世系信息是解决以上问题的有效方法。因此，本文采用一种开源的系统调用追踪工具Progger ^{[10, 21]}，从Progger日志（Progger log，P-Log）中获取Hadoop宿主机的本地操作信息，如表1所示。除归约信息外，P-Log的每条记录还包括进程ID（process ID，PID）、会话组ID（session ID，SID）等。P-Log格式可参考文献[10]。

综上，在各日志信息存在重合的情况下，针对给定的世系信息，综合考虑各日志所包含信息的完备性与相关性，采用HA-Log、FsImage、EditLog、HttpFS审计日志（HttpFS audit log, HTA-Log）、JNN-Log、AS-Log、作业配置文件（job configuration file, JC-File）、AC-Log、P-Log和hosts文件能够获得各指定世系实例的全部属性信息。Step 3-1完成。

3.2.2　多日志关联

从表1中可以看出，很多世系类型的属性信息来源于多个日志。本小节执行Step 3-2，证明对于这些世系类型，相关的日志记录类型均能够正确关联并完整包含在给定条件下产生的世系实例。

采用完全归纳法对各世系类型进行证明发现，对于不同日志中的相关记录，绝大部分可以通过公有属性进行关联并满足世系完整性的条件2。图3展示了各日志间可作为关联媒介的公有属性。不直接相连的日志能够以中间日志为媒介进行关联。例如，对于非NFS模式下的HFile读取，从Hadoop日志中无法获得操作的结束时间。但HFile读取会引起E4File读取。P-Log中HFile最后一个被读取E4File的关闭记录（“SYS_CLOSE”）时间戳即为HFile读取的结束时间。关于该操作，HA-Log和P-Log缺乏公共属性，但能够以EditLog为媒介；首先通过HA-Log记录的文件路径从EditLog中获取其数据块集合，然后利用数据块ID连接到P-Log中相应块文件的“SYS_CLOSE”记录。由于篇幅限制，本文不在此展开介绍全部的日志关联过程。

此外，仅当HDFSFile操作的执行者为软件代理时，在建立活动与代理之间的关联关系时无法在Hadoop日志与P-Log的相关记录间找到关联媒介，需要利用Hadoop的运行原理建立日志记录间的关联。总体思路是首先在P-Log中找到Hadoop日志所记录操作的执行进程，而后判断该进程是否为软件代理进程。若是，则可建立相应的关联关系。

若操作执行者为软件代理，操作必然发生在Hadoop节点上。若操作执行模式为CLI或WebHDFS，操作执行进程会首先和NameNode进程建立TCP连接。若采用HttpFS模式，连接对象为HttpFS服务器。在P-Log中，上述活动由“SYS_CONNECT”记录表达。记录SID值是操作执行进程的PID。

利用上述原理，首先按照Hadoop日志记录的操作执行模式与时间信息，在P-Log中查找相应的“SYS_CONNECT”记录，得到操作执行进程（假设为p₁），将Hadoop日志与P-Log的相关记录关联起来。

然后，根据p₁的PID值判断其是否为特定软件代理。以Container为例，图4所示记录（Progger: 0表示“SYS_OPEN”）表示一个“bash”进程打开“launch_container.sh”，可看作Container的启动标志。图中Container进程的PID为5029，以灰色底纹突出显示。利用p₁的PID值，在“SYS_CONNECT”之前的记录中查找具有相同PID的Container启动记录。若能找到，说明操作由此Container执行。

综上，对于指定的世系类型，本节运用提出的世系完整性证明方法，证明了在HDFS支持的操作执行模式和给定的代理类型条件下，各类世系实例的属性信息都包含于归约的日志中，并且相关日志记录能够正确关联以完整包含世系实例集合。

4　 结 语

本文针对大数据场景下，基于多日志分析世系生成的可行性证明问题，利用多日志归约与关联，首次提出了一种形式化证明方法，填补了学术界针对该问题的研究空白。其中，针对所含元素分散在多个日志中的世系类型，提出了两种基于日志公共元素与基于程序运行原理的日志关联方法。针对Hadoop，证明了采用多日志分析方法生成Hadoop数据世系是可行的，为日志分析方法的研究奠定了基础。

参考文献

[1] GLAVIC B. Big data provenance： Challenges and implications for benchmarking［C］//Specifying Big Data Benchmarks. Heidelberg： Springer， 2012： 72-80. DOI： 10.1007/978-3-642-53974-9_7 .

[2] SUEN C H， KO R K L， TAN Y S， et al. S2Logger： End-to-end data tracking mechanism for cloud data provenance［C］//2013 12th IEEE International Conference on Trust， Security and Privacy in Computing and Communications. New York： IEEE Press， 2013： 594-602. DOI： 10.1109/TrustCom.2013.73 .

[3] HASSAN W U， NOUREDDINE M A， DATTA P， et al. OmegaLog： High-fidelity attack investigation via transparent multi-layer log analysis［C］//Network and Distributed System Security Symposium. Reston： Internet Society， 2020： 1-16. DOI： 10.14722/ndss.2020.24270 .

[4] PÉREZ B， RUBIO J， SÁENZ-ADÁN C. A systematic review of provenance systems［J］. Knowledge and Information Systems， 2018， 57（3）： 495-543. DOI： 10.1007/s10115-018-1164-3 .

[5] PASQUIER T， HAN X Y， GOLDSTEIN M， et al. Practical whole-system provenance capture［C］//Proceedings of the 2017 Symposium on Cloud Computing.. New York： ACM， 2017： 405-418. DOI： 10.1145/3127479.3129249 .

[6] YU L， MA S Q， ZHANG Z， et al. ALchemist： Fusing application and audit logs for precise attack provenance without instrumentation［C］//Proceedings of the Network and Distributed System Security Symposium. Reston： Internet Society， 2021： 1-18. DOI： 10.14722/ndss.2021.24445 .

[7] GHOSHAL D， PLALE B. Provenance from log files： A BigData problem［C］//Proceedings of the Joint EDBT/ICDT 2013 Workshops. New York： ACM， 2013： 290-297. DOI： 10.1145/2457317.2457366 .

[8] ABBADI I M， LYLE J. Challenges for provenance in cloud computing［C］//The 3rd USENIX Workshop on the Theory and Practice of Provenance. Heraklion： USENIX， 2011： 1-6.

[9] CHAN S C， GEHANI A， IRSHAD H， et al. Integrity checking and abnormality detection of provenance records［C］//The 12th International Workshop on Theory and Practice of Provenance. Berkeley： USENIX， 2020： 1-6. DOI: 10.1145/3361525.3361552 .

[10] KO R K L， WILL M A. Progger： An efficient， tamper-evident kernel-space logger for cloud data provenance tracking［C］//2014 IEEE 7th International Conference on Cloud Computing. New York： IEEE Press， 2014： 881-889. DOI： 10.1109/CLOUD.2014.121 .

[11] 明华， 张勇， 符小辉. 数据溯源技术综述［J］. 小型微型计算机系统， 2012， 33（9）： 1917-1923. DOI： 10.3969/j.issn.1000-1220.2012.09.009 .

[12] MING H， ZHANG Y， FU X H. Survey of data provenance［J］. Journal of Chinese Computer Systems， 2012， 33（9）： 1917-1923. DOI： 10.3969/j.issn.1000-1220.2012.09.009（Ch ）.

[13] 戴超凡， 王涛， 张鹏程. 数据起源技术发展研究综述［J］. 计算机应用研究， 2010， 27（9）： 3215-3221. DOI： 10.3969/j.issn.1001-3695.2010.09.004 .

[14] DAI C F， WANG T， ZHANG P C. Survey of data provenance technique［J］. Application Research of Computers， 2010， 27（9）： 3215-3221. DOI： 10.3969/j.issn.1001-3695.2010.09.004（Ch ）.

[15] WANG Y R， MADNICK S E. A polygen model for heterogeneous database systems： The source tagging perspective［C］// The 16th International Conference on Very Large Data Bases. New York： ACM， 1990： 519-538. DOI： 10.5555/645916.758355 .

[16] SIMMHAN Y， GROTH P， MOREAU L. Special Section： The third provenance challenge on using the open provenance model for interoperability［J］. Future Generation Computer Systems， 2011， 27（6）： 737-742. DOI： 10.1016/j.future.2010.11.020 .

[17] MOREAU L， GROTH P， CHENEY J， et al. The rationale of PROV［J］. Journal of Web Semantics， 2015， 35： 235-257. DOI： 10.1016/j.websem.2015.04.001 .

[18] GAO Y Z， CHEN X Y， DU X H. A big data provenance model for data security supervision based on PROV-DM model［J］. IEEE Access， 2020， 8： 38742-38752. DOI： 10.1109/ACCESS.2020.2975820 .

[19] GEWUZHAO. Big-data-provenance-ontology［EB/OL］. ［2021-02-03］.

[20] RUPPRECHT L， DAVIS J C， ARNOLD C， et al. Improving reproducibility of data science pipelines through transparent provenance capture［J］. Proceedings of the VLDB Endowment， 2020， 13（12）： 3354-3368. DOI： 10.14778/3415478.3415556 .

[21] DATTA P， POLINSKY I， INAM M A， et al. ALASTOR： Reconstructing the provenance of serverless intrusions［C］//Proceedings of the 31st USENIX Security Symposium. Boston： USENIX. 2022： 2443-2460. DOI： 978-1-939133-31-1 .

[22] 金国栋， 卞昊穹， 陈跃国， 等. HDFS存储和优化技术研究综述［J］. 软件学报， 2020， 31（1）： 137-161. DOI： 10.13328/j.cnki.jos.005872 .

[23] JIN G D， BIAN H Q， CHEN Y G， et al. Survey on storage and optimization techniques of HDFS［J］. Journal of Software， 2020， 31（1）： 137-161. DOI： 10.13328/j.cnki.jos.005872（Ch ）.

[24] CORRICK T J C. Progger 3： A Low-overhead， Tamper-proof Provenance System［D］. Hamilton： The University of Waikato， 2021. DOI: 10.1007/978-981-19-0468-4_14 .

基金资助

国家重点研发计划(2018YFB0803603)

科技创新特区资助项目(18-H863-01-ZT-005-017-01)