PDF溯源入门
更好地理解数据需要跟踪其历史和上下文。
Lucian Carata, Sherif Akoush, Nikilesh Balakrishnan, Thomas Bytheway, Ripduman Sohan, Margo Seltzer, Andy Hopper
评估数据的质量或有效性通常不是孤立完成的。您通常会检查数据出现的上下文，并尝试确定其原始来源或审查其创建过程。然而，当处理数字数据时，情况并非如此简单：计算结果可能来源于众多来源，并通过复杂的连续转换得出，可能历时很长时间。
随着构成特定结果的数据量增加，跟踪不同来源和转换之间的相互关系变得更加困难。这限制了回答关于结果历史的问题的能力，例如：结果所基于的潜在假设是什么？它在什么条件下仍然有效？还有哪些结果来源于相同的数据源？
需要系统地捕获以回答这些（或类似）问题的元数据被称为溯源（或沿袭），它指的是描述构成数据存在的所有元素（来源、处理步骤、上下文信息和依赖关系）之间关系的图。
本文从实践的角度介绍了该领域当前的研究，不仅讨论了现有系统以及今天在应用程序中使用它们所需的基本概念，还讨论了未来的挑战和机遇。一些用例说明了溯源在实践中可能有多么有用。
数据从何而来？
考虑需要理解给定结果背后的条件、参数或假设——换句话说，能够指向一段数据，例如研究结果或系统跟踪中的异常，并询问：它从何而来？ 这对于涉及数字数据的实验（例如生物学中的计算机模拟实验、其他类型的数值模拟或计算机科学中的系统评估）非常有用。
此类实验每次运行的溯源都包含结果与相应的起始条件或配置参数之间的链接。当考虑处理管道时，这一点尤其重要，在处理管道中，一些早期结果是进一步实验的基础。手动跟踪从最终结果到中间数据再到原始来源的所有参数是繁琐且容易出错的。
当然，研究人员不是唯一需要这种类型跟踪的人。相同的技术可以用于帮助商业或金融领域的人员——例如，找出董事会报告的统计数据背后的一系列假设，或确定哪些抵押贷款是交易证券的一部分。
谁在使用这些数据？
您可以捕获溯源以了解结果的后续使用位置，或者找出哪些数据是从该结果进一步派生的，而不是将结果追溯到其来源。例如，一家公司可能想要识别某个代码片段的所有内部用途，以便遵守许可协议或跟踪仍在使用需要删除的已弃用或不安全功能的代码。
使用类似的机制，最终用户应该能够跟踪移动应用程序使用了哪些个人信息，并确定它是在本地显示还是通过网络发送给第三方。当我们需要了解哪些数据因发现错误而失效时，同样的用例涵盖了错误结果的普遍传播。
如何获得？
溯源还可以用于更好地理解输入数据被转换为输出数据的实际过程。这在计算机工程师或系统管理员需要调试运行复杂软件堆栈时出现的问题时非常重要。
在可以区分正确和错误系统输出的情况下，比较它们的溯源将指出错误的潜在根本原因列表。在更复杂的情况下，问题可能并非直接链接到特定输出，而是链接到（不期望的）行为变化。检测系统入侵或解释服务器的响应尾部延迟增加 20% 就是很好的例子。在这些情况下，将具有相似溯源的输出分组可以用于识别正常与异常系统行为，并解释两者之间的差异。
溯源系统
这三个用例共同概述了理想的溯源应用领域，但它们并未描述使这些应用成为可能的技术细节。为了在实践中实现每个场景，需要将一个或多个溯源系统集成到数据处理工作流程中，负责捕获溯源、在相关组件之间传播溯源，并使其可供用户查询。
在许多方面，您可能已经在运行此类系统的专用版本：所有审计、跟踪框架或变更跟踪解决方案都收集某种形式的溯源，即使它们可能没有将其识别为溯源。将溯源视为独立概念的优势在于能够以原则性的方式使用此元数据，从而允许结果可验证性和复杂的历史查询，而无需考虑用于收集它的底层机制以及跨应用程序和软件堆栈。
从历史上看，溯源系统是数据库领域研究的重点，目的是了解在底层表发生更改时应如何以及何时更新物化视图。9 由于定义明确的关系模型，因此既可以从查询中导出精确的溯源信息7，又可以开发允许简洁表示的形式化方法。13 这已在 Trio28 等系统中得到进一步扩展，允许记录合并相关的不确定性，不确定性可以通过使用溯源在多个查询中传播。
相比之下，对于执行任意计算（不限于一小组有效转换）的应用程序捕获溯源已被证明更具挑战性。该领域的研究工作主要集中在软件堆栈中特定点的溯源收集（通过修改应用程序、运行时环境或内核）。
图 1 展示了溯源系统的一般时间线。本文着眼于其中八个系统（PASS、SPADE、VisTrails、ZOOM、Burrito、Lipstick 和 RAMP）的特性，每个系统都代表了更大一类解决方案
操作系统级别。 PASS22,23 和 SPADE12 通过观察应用程序事件（例如进程创建或 I/O）来研究溯源。然后将这些事件用于推断不同数据片段之间的依赖关系。
工作流程。 VisTrails26 和 ZOOM2 是工作流程管理系统，能够跟踪各种工作流程执行的溯源，以及（在 VisTrails 的情况下）工作流程本身的演变。
应用程序级别。Burrito14 跟踪用户空间事件，同时还支持用户提供的其他注释。SPROV16 专注于溯源的安全性，并围绕标准 C I/O 库提供了一个薄包装器。较新版本能够使用其他系统（例如 PASS）捕获的溯源。
大数据。Lipstick1 和 RAMP24 都解决了大数据场景（MapReduce 作业）中跟踪溯源的问题。
正是这些系统的属性定义了可以记录什么以及以何种权衡、开销和安全影响进行记录。
溯源系统属性
在实践中有效使用溯源系统需要理解与以下方面相关的许多方面：
• 正在捕获的确切元数据。
• 将溯源系统集成到现有工作流程中所需的工作量（运行特殊的内核、进行运行时更改或将应用程序与溯源库链接）。
• 了解稍后如何查询溯源元数据。
• 评估这些系统施加的开销。
• 溯源添加的安全问题，可能需要与数据本身不同的访问控制。
本文根据这些特征（汇总在表 1 中）对选定的代表性系统的属性进行分类，并在需要时参考激励用例。
它可以捕获什么？
溯源系统捕获的元数据通常将数字实体（文件、表、程序、网络连接等）在其生命周期中不同阶段的状态与其对其他实体或进程的历史依赖关系相关联。在这种情况下，两个概念对于确定捕获什么以及如何捕获至关重要：粒度和分层。
粒度。 捕获的粒度是指在系统中累积溯源的基本原语的大小。考虑一位科学家使用一个配置文件，该文件存储各种实验参数作为模拟程序的输入之一。以文件粒度捕获溯源将建立模拟程序和配置文件名之间的依赖关系。然而，科学家感兴趣的是理解模拟结果和文件中各个参数之间的关系，这需要以子文件粒度进行捕获。
不同粒度（从细到粗）的确切含义也取决于应用程序的底层数据模型。例如，数据库溯源系统可以存储整个表、表中的行或每个单元格的溯源元数据。表级别的溯源捕获是粗粒度的，可以回答诸如：表 X 从哪些其他表派生了其数据？更精细的粒度将确定各个行或单元格之间的关系。当然，可以同时考虑多个粒度。
PASS6 等系统通过拦截应用程序执行时发出的系统调用来捕获溯源。在此级别，溯源是细粒度的，可以提供应用程序执行和依赖关系的详细图像。
然而，收集的数据中的噪声水平也升高了，使得提取有用的信息更加困难。考虑一个将一个文件复制到另一个文件的 Python 脚本。当运行脚本时，Python 解释器将首先从磁盘读取和加载任何必需的模块。因此，除了对实际输入的依赖之外，最终溯源图还将输出文件链接到解释器使用的所有 Python 模块。这种额外的数据会使最终用户难以筛选溯源图，因此，通常需要启发式方法来确定哪些实体是重要的，哪些应该被忽略。
VisTrails26 等工作流程系统避免了噪声问题，并且可以捕获任何粒度的溯源，因为处理步骤及其依赖关系由最终用户显式声明。然而，此类系统本质上也仅限于记录仅那些属于已定义工作流程的数据转换。
n 对 m 问题。 独立于所选择的系统，准确确定输入和输出数据之间的依赖关系可能是不可能的。n 对 m 问题说明了这一点，其中程序读取 n 个输入文件并写入 m 个输出文件。即使跟踪单个读取和写入的系统调用，也不可能推断出哪些读取影响了特定的写入，因此溯源图必须将每个输出文件链接到所有输入。一个不了解进程中单个数据转换语义的系统将始终呈现许多此类误报关系。PASS 和 VisTrails 都存在这个问题，因为它们将进程或每个工作流程步骤都视为黑盒。
n 对 m 问题可以通过以更精细的粒度捕获溯源来解决。这可以使用二进制插桩技术25 来完成，并将输出的溯源计算为执行的代码路径和数据依赖关系的函数。即使此方法不需要修改应用程序，但权衡是空间和时间开销显着增加。一种低开销的替代方案是修改应用程序以使用诸如 CPL17 之类的 API 显式披露相关溯源，但这需要开发人员付出额外的努力，如下节所述。
粒度不是用户在确定其对溯源系统的要求时需要考虑的唯一方面。了解溯源收集发生在哪个层也同样重要。
分层。溯源元数据可以在堆栈中的多个层（即，对于应用程序、中间件（运行时/库）、操作系统和/或硬件）中捕获。跨多个层捕获溯源为用户提供了在不同的抽象级别推理其数据和进程的能力，每一层都提供了对系统中发生的同一组事件的不同视图。
例如，考虑在电子表格中的两个表之间复制行并保存结果。一个在操作系统层收集溯源的系统将观察到许多进出文件的 I/O 操作。然而，表和行的概念仅为应用程序所知，并且它们之间的依赖关系无法从较低层收集的元数据中推断出来。如果需要查询此类关系，则还必须在应用程序层中捕获溯源。
层之间的合作。 当需要在多个层捕获溯源时，从业者可以为堆栈中的每一层选择不同的（专门的）溯源系统，或者选择一个旨在跨多个层捕获的单个溯源系统。
在这两种情况下，多个支持溯源的组件都必须通过在层之间传递不同的元数据来协作。这可以通过遵循通用的溯源数据模型来实现，例如 OPM（开放溯源模型）21 或 PROV-DM20 （溯源数据模型），或者通过提供通用 API 并允许每个组件接受和生成溯源来实现。PASSv2 提供了一个披露的溯源 API (DPAPI)，可用于此目的。
然而，还存在第二个问题。仅仅在不同层收集元数据将导致彼此不相关的溯源孤岛。为了实现层之间溯源对象的实际映射，必须将描述同一事件的所有实体分组在一起——例如，通过使用唯一标识符标记它们。
例如，SPADEv2 使用多源融合过滤器（以进程 ID 作为标记）来组合来自多个源的溯源数据，这些数据描述了同一事件并在同一抽象级别工作。当在不同抽象级别报告溯源时，SPADEv2 使用具有相同目的的跨层组合过滤器。
数据版本控制。给定层中的溯源收集通常涉及捕获应用程序在给定数据片段上执行的一系列事件，但这不一定要求系统捕获正在转换的数据的多个版本。假设用户在使用支持 PASS 的系统上的文本编辑器编辑文件。PASS 保存的溯源元数据可以提供诸如用于编辑的程序、写入文件的字节数等信息，但无法将文件恢复到以前的状态或知道实际的数据更改是什么。在文件的当前内容取决于先前版本的值的情况下，溯源系统需要存储数据版本以及事件，以确保完全可验证性。
因此，Burrito14 等溯源系统不仅跟踪系统调用级别的事件，还在版本控制文件系统之上运行。Lipstick 和 RAMP 等其他系统不需要版本控制，因为它们在仅追加文件系统之上运行（所有版本都隐式存储）。
当对堆栈中的某些层（即，对于硬件寄存器）进行版本控制时，版本控制可能会被证明是昂贵的，但在其他情况下，它可能会简化溯源的捕获。应用程序层就是这种情况，其中数据版本作为撤消/重做操作隐式存储。大多数 GUI 应用程序默认提供此功能，并且拦截撤消堆栈已被证明是自动推断溯源的可行方法。8
将溯源集成到现有工作流程中
在选择溯源系统时，将新技术集成到现有工作流程中所需的工作量是一个重要的实际标准。这衡量了溯源系统将在多大程度上侵入用户的正常工作习惯，并且应根据用例进行成本效益分析。
由于某些系统收集元数据的方式，它们会带来更大的前期费用。例如，某些系统要求开发人员通过 API 明确证明溯源信息，这些 API 记录关于正在执行的操作的注释。DPAPI 就是一个例子，它提供了增强的读取和写入调用，您可以在其中传递指示正在进行的读取或写入调用的含义的数据。结果是开发工作量增加，因为必须更新代码才能调用新的 API。所有未来的代码更改也必须保持与溯源相关的代码同步，并且未能这样做很可能会导致捕获无效的元数据。
同样，ZOOM 或 VisTrails 等系统要求您预先声明整个工作流程，并且只能跟踪那些在其执行引擎之上运行的依赖关系。如果需要维护依赖关系链接，则必须在同一系统中完成后续工作。作为一个群体，文献将这些称为披露的溯源系统，并且它们因能够提供改进的溯源语义描述而受到认可。然而，在这种方式捕获的溯源的可信度是在不受信任的环境中运行时的一个问题。
其他溯源系统旨在减少用户承担的开销。这些系统倾向于采用不同的方法，即观察用户的应用程序，记录有关这些应用程序如何相互交互以及与操作系统的其余部分交互的信息，并基于此推断溯源。它们通常被称为观察到的溯源系统。示例系统包括 PASS，它拦截程序发出的系统调用，或者 SPADE 等其他系统，它可以挂钩到 Linux 内核中的审计子系统以观察程序的动作。它们往往具有最低的侵入性。通常，一旦安装了系统，用户就可以像往常一样继续操作，同时为所有执行的操作捕获溯源。然而，观察到的溯源系统也有其自身的缺点，主要是因为在将每个进程视为黑盒时会丢失语义信息。
您如何使用溯源回答问题？
溯源系统的用途仅与其可以基于收集的元数据回答的问题一样有用。然而，查询被认为是一个具有挑战性的问题：用户通常想要查询范围广泛的信息，或者他们提出溯源系统设计者没有预料到的问题；根据捕获的粒度，系统可能没有足够的数据来响应查询，或者它可能产生太多的数据以至于难以探索和理解。从该领域迄今为止进行的研究来看，已经出现了两种核心查询范例，并且少数系统使用了两种方法的混合。
探索性。第一个主要范例是探索性查询，它利用了人类发现模式的能力。当用户不确切知道他们可能想要检索哪些元数据时，这非常重要。探索性系统的特点通常是向用户呈现溯源图的可视化表示，并提供工具来探索它而不会屈服于信息过载。这是一个非常困难的问题，因为即使是小的溯源图也很容易包含数千个节点。许多方法都涉及基于上下文过滤（例如 InProv4）探索子图，或使用智能聚类方法。后者的一个例子是 PASS Map Orbiter18 查看器，它实现了一种用于动态汇总节点的算法，允许用户在浏览时展开和收缩细节区域。
定向。第二个主要范例是定向查询，这种方法更接近于经典的数据库查询领域。它要求用户以一种语言（通常是 SQL 的专门扩展或路径查询语言）表达关于数据溯源的问题作为查询。如果用户确切知道需要哪些信息，则此方法是有效的，但与探索性方法不同，定向查询方法不利于发现关于溯源图的新见解。
定向方法的一个例子是 vtPQL，26 用于 VisTrails 系统。该语言旨在使用户能够表达关于工作流程三个不同方面的溯源查询：执行日志、抽象工作流程表示和工作流程在时间上的演变。
用户可以同时指定对所有这些空间的限制——例如，将执行日志限制为特定日期，突出显示单个工作流程模块，以及选择特定版本的工作流程。这很有帮助，因为它允许用户从正交查询关注点的角度进行思考。
混合。一些系统使用这两种范例的混合。例如，ZOOM 系统2 从用户提供的“兴趣声明”开始，以导出上下文相关的最小形式的溯源图。该系统的核心是一种算法，该算法以保持其语义的方式汇总了图的“不相关”部分。用户只需要提供工作流程定义中感兴趣的模块列表，然后就可以浏览溯源图，而不会因不重要的信息片段而分心。
理解开销
与任何计算功能一样，溯源捕获也具有相关的时间和空间成本。鉴于溯源支持很可能成为系统主要功能的附加考虑因素，仅在需要数据的沿袭属性时才使用，因此必须最大限度地减少开销。
通用溯源系统通常捕获给定工作流程的（披露的）演变或执行进程执行的（观察到的）低级操作。广义上讲，捕获工作流程演变的溯源的时间和空间开销与工作流程中更改的数量以及工作流程执行的次数成正比。相比之下，捕获执行日志的溯源开销与记录的可记录操作的数量成正比。
时间开销。在实践中，工作流程系统（以及扩展的其他披露的溯源系统）的溯源捕获成本微乎其微，因为它们收集运行进程信息的方法有限。例如，ZOOM 和 VisTrails 都报告执行时间大约增加了 1%。2,10
对于记录进程执行的系统，溯源捕获成本是拦截和记录可观察操作的成本的函数。虽然直观上操作级别的溯源捕获从时间角度来看可能非常昂贵，但报告的结果表明事实并非如此。基于内核的系统调用拦截机制（例如 PASSv2 中的机制）在代表真实世界应用程序的工作负载上具有 1% 到 23% 的开销。22,23 同样，SPADEv2 使用内核审计基础设施进行溯源捕获，报告在 Windows、Linux 和 OS X 上生产 Apache 运行的开销小于 10%。12
然而，对于 I/O 密集型工作负载，溯源捕获可能会带来更大的运行时开销。例如，PASS 报告在小文件基准测试中高达 230% 的开销23，即使执行时间的绝对增加仍然很小。
拦截机制也可能在这方面显着影响溯源捕获开销。例如，SPADEv2 支持通过 OS X 上的内核审计机制拦截操作，而 Windows 则需要文件系统过滤器驱动程序，该驱动程序将操作中继到溯源收集器。因此，启用溯源的 Apache 构建在 Windows 上慢 50%，但在 OS X 上仅慢 5%。
在以极细粒度级别记录溯源的情况下，记录操作的时间成本也可能引起潜在的关注。在这种情况下，溯源捕获的成本通常等于或超过记录操作的成本，从而导致超过 100% 的减速。例如，在 Lipstick 系统中，据报告操作员级别的溯源会导致两到三倍的减速1，而在 RAMP 系统中，通过在 MapReduce 工作流程中传播标签在元组级别收集溯源，通常会观察到高达 75% 的时间开销。24
空间开销。与时间开销类似，记录进程执行的空间开销是每个操作的数据量和记录的操作数量的函数。在我们研究的系统集中，只有一半（SPROV、Burrito、Lipstick 和 RAMP）能够记录数据更改。
虽然任何工作负载的实际开销都对多个因素敏感，但以下是为说明目的报告的两个数据点：
• 通用 PASSv2 系统平均需要大约 20% 的额外空间开销（与原始输出大小相比）来记录代表真实世界应用程序的工作负载的所有操作。22
• Burrito 系统在真实用户工作负载上运行，在两个月的时间内需要 800 MB 的溯源存储空间和 2 GB 的文件版本。14
这些结果表明，对于大多数情况，存储开销不应过高。
开销权衡。一般来说，捕获粒度与溯源开销之间存在直接的权衡。例如，SPADEv2 允许用户以函数调用级别或应用程序定义的级别捕获信息，但代价是增加了时间和空间捕获开销。同样，SPROV 允许用户指定更高级别语义的修改（例如，“已向文件添加新节”），但代价是降低了每次操作的可观察性。
为了让用户采用最适合其需求的系统，用户可能需要预先确定回答查询需要哪些溯源信息以及此信息在什么粒度下就足够了，并将其映射到适当的系统。
大多数系统还会延迟溯源构建，以最大限度地减少捕获开销。例如，PASSv2 捕获原始操作记录，并通过异步用户空间守护程序将其转换为最终表示形式。22 SPADEv2 使用单独的溯源收集线程来提取、过滤操作并将操作提交到溯源日志。其他系统将溯源收集延迟到查询时间，以避免浪费资源计算永远不会被访问的溯源。例如，Lipstick 仅在发出查询时才执行溯源构建。1 延迟溯源构建也存在于一些工作流程系统中。例如，ZOOM 将在查询时根据当前用户视图计算一些溯源。根据溯源查询的所需基数、及时性和复杂性，决定这些权衡可能会大大提高开销。
安全问题
必须确保溯源数据的安全，防止未经授权的访问，并且不泄露有关其收集的数据的任何信息。5 从根本上说，这要求溯源在与数据不同的访问策略下进行管理。这样做使用户可以灵活地控制溯源信息的披露。例如，人们可能会使组织外部的人员无法访问溯源，因为它会泄露专有工作流程或流程。然而，最终的数据结果可能对任何人免费开放。
形式上，溯源的安全方面被定义为其机密性（只有授权方可以读取它）及其完整性（它不能被伪造或更改）。这两个属性都被认为是对数据执行完整性、验证和一致性检查必不可少的。
已经提出了两种解决提供安全溯源问题的方法。第一种方法利用了参考监视器的概念：Patrick McDaniel 等人讨论了一种基于主机防篡改溯源监视器原则的端到端安全溯源系统，该监视器镜像了用于强制执行安全策略的众所周知的参考监视器概念。19 参考监视器的存在意味着溯源收集的安全性不必依赖于其他系统组件（例如内核）的完整性。虽然此解决方案是可行的，但迄今为止尚无已知的实际实现。
第二种解决方案基于溯源链11,16，其中生成溯源的进程必须以加密、不可修改和不可否认的方式证明添加的信息。保证这三个属性可确保所有收集的溯源都可以保持机密性并保持其完整性。在本文包含的系统中，SPROV16 是溯源链的实际实现。它主要为文件修改提供机密性和完整性保证。SPROV 利用密码学中的许多概念来满足安全要求：通过加密描述每个更改的元数据来维护机密性；通过校验和记录来维护记录完整性；并通过使用创建用户的公钥签名记录来支持证明。
除了机密性和完整性的关键概念之外，SPROV 还提供许多对从业者可能感兴趣的有用功能（以及对未来安全溯源系统的考虑）：通过使用密码学承诺，3 SPROV 能够选择性地向第三方公开记录；通过采用广播加密，15 它支持对多个审计员的选择性访问控制，而无需相应地成比例地增加密钥数量；最后，支持阈值加密27，从而实现职责分离的场景，其中记录的解密需要来自多个不同组中的至少一个审计员的参与。
SPROV 没有防止未经授权读取的机制，而是依赖于记录加密来防止未经授权的访问。然而，它是此处包含的系统中唯一提供任何溯源机密性和完整性保证的系统。虽然所有系统都承认溯源的安全性是一个基本问题，但其余系统都依赖于现有的访问控制机制，例如 SQL 授予权限和文件权限，以确保安全性。
研究挑战与机遇
将初始用例与当前溯源系统实际可以实现的目标进行对比，清楚地表明在许多领域都需要研究。
查询和可视化。 尽管目前已针对溯源的查询和可视化进行了研究，但这些仍然是具有挑战性的问题。 现有的关于图探索和可视化的知识如何应用，或者是否需要完全不同的表示形式，仍有待观察。
使用溯源进行计算。 除了人工查询之外，溯源应该提供给应用程序使用，从而实现输入的自动验证、限制错误传播或自诊断输出质量或系统行为的变化。
分布式系统。 已经有人尝试将溯源扩展到网络系统，但与异构性（并非所有节点都具有溯源意识）、可扩展性、长期收集和存储相关的问题仍有待解决。
安全和隐私。 收集溯源会影响数据安全和隐私，但大多数实现方式尚未考虑不受信任的环境或对抗性工作负载。
结论
如今可用的计算能力和存储容量允许以复杂的方式处理大量数据。 有时，应用的转换并非直接受开发人员控制，甚至不为开发人员所知（多层抽象、学习算法）。 因此，当没有记录溯源时，关于结果的许多信息会丢失，从而更难以评估质量或可重复性。 计算正变得无处不在，对计算可靠性的保证需求只会加剧这些问题； 将溯源视为数据处理中的一等公民代表了一种可能的解决方案。
致谢
我们要感谢 George Coulouris 在将本文塑造成当前形式的过程中提供的反馈和支持，以及审稿人提出的建设性意见和建议。
参考文献
1. Amsterdamer, Y., et al. 2011. Putting lipstick on pig: enabling database-style workflow provenance. In Proceedings of the VLDB Endowment 5(4): 346-357.
2. Biton, O., Cohen-Boulakia, S., Davidson, S. B. 2007. ZOOM*UserViews: querying relevant provenance in workflow systems. In Proceedings of the 33rd International Conference on Very Large Databases: 1366-1369.
3. Blum, M. 1982. Coin flipping by telephone: a protocol for solving impossible problems. In Advances in Cryptology—A Report on CRYPTO '81.
4. Borkin, M. A., et al. 2013. Evaluation of filesystem provenance visualization tools. In IEEE Transactions on Visualization and Computer Graphics 19(12): 2476-2485.
5. Braun, U., Shinnar, A., Seltzer, M. 2008. Securing provenance. In the 3rd Usenix Workshop on Hot Topics in Security: 1-5.
6. Braun, U., et al. 2006. Issues in automatic provenance collection. In Proceedings of the International Conference on Provenance and Annotation of Data: 171-183.
7. Buneman, P., Khanna, S., Tan, W.-C. 2002. Why and where: a characterization of data provenance. In Proceedings of the 8th International Conference on Database Theory: 316-330.
8. Callahan, S. P., et al. 2008. Towards process provenance for existing applications. In Proceedings of the 2nd International Provenance and Annotation Workshop: 120-127.
9. Cui, Y., Widom, J., Wiener, J. L. 2000. Tracing the lineage of view data in a warehousing environment. Transactions on Database Systems 25(2): 179-227.
10. Freire, J., et al. 2006. Managing rapidly evolving scientific workflows. In Proceedings of the International Conference on Provenance and Annotation of Data: 10-18.
11. Gates, C., Bishop, M. 2011. One of these records is not like the others. In Proceedings of the 3rd Usenix Workshop on the Theory and Practice of Provenance.
12. Gehani, A., Tariq, D. 2012. SPADE: support for provenance auditing in distributed environments. Proceedings of the 13th International Middleware Conference: 101-120.
13. Green, T. J., Karvounarakis, G., Tannen, V. 2007. Provenance semirings. In Proceedings of the 26th SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems: 31-40.
14. Guo, P. J., Seltzer, M. 2012. Burrito: wrapping your lab notebook in computational infrastructure. In Proceedings of the 4th Usenix Conference on Theory and Practice of Provenance: 7-7.
15. Halevy, D., Shamir, A. 2002. The LSD broadcast encryption scheme. In Advances in Cryptology:47-60.
16. Hasan, R., Sion, R., Winslett, M. 2009. The case of the fake Picasso: preventing history forgery with secure provenance. In Proceedings of the 7th Conference on File and Storage Technologies: 1-14.
17. Macko, P., Seltzer, M. 2012. A general-purpose provenance library. In Proceedings of the 4th Usenix Conference on Theory and Practice of Provenance: 6-6.
18. Macko, P., Seltzer, M. 2011. Provenance Map Orbiter: interactive exploration of large provenance graphs. In Proceedings of the 3rd Conference on Theory and Practice of Provenance.
19. McDaniel, P., et al. 2010. Towards a secure and efficient system for end-to-end provenance. In Proceedings of the 2nd Conference on Theory and Practice of Provenance: 2-2.
20. Moreau, L., Missier, P. 2013. PROV-DM: the PROV Data Model. Technical Report. World Wide Web Consortium; http://www.w3.org/TR/prov-dm/.
21. Moreau, L., et al. 2011. The Open Provenance Model Core Specification (V1.1). Future Generations Computer Systems 27(6): 743-756.
22. Muniswamy-Reddy, K.-K., et al. 2009. Layering in provenance systems. In Proceedings of the Usenix Annual Technical Conference.
23. Muniswamy-Reddy, K.-K., et al. 2006. Provenance-aware storage systems. In Proceedings of the Usenix Annual Technical Conference: 43-56.
24. Park, H., Ikeda, R., Widom, J. 2011. RAMP: a system for capturing and tracing provenance in MapReduce workflows. The 37th International Conference on Very Large Databases.
25. Saxena, P., Sekar, R., Puranik, V. 2008. Efficient fine-grained binary instrumentation with applications to taint-tracking. In Proceedings of the 6th Annual IEEE/ International Symposium on Code Generation and Optimization: 74-83.
26. Scheidegger, C., et al. 2008. Tackling the provenance challenge one layer at a time. Concurrency and Computation: Practice and Experience 20(5): 473-483.
27. Shamir, A. 1979. How to share a secret. Communications of the 22(11): 612-613.
28. Widom, J. 2004. Trio: a system for integrated management of data, accuracy, and lineage. Technical Report 2004-40.
喜欢或不喜欢？请告诉我们
Lucian Carata ([email protected]) 是剑桥大学计算机实验室的博士研究生。 他的研究重点是下一代公开溯源系统，旨在理解和控制复杂系统的行为。
Sherif Akoush ([email protected]) 是剑桥大学计算机实验室的研究助理。 他正在探索“大数据”系统（例如 MapReduce）中的溯源及其应用。 他还对节能计算和为新兴地区开发新技术感兴趣。
Nikilesh Balakrishnan ([email protected]) 是剑桥大学计算机实验室的研究助理。 他的研究重点是构建通用溯源系统，重点关注用户社区的可用性和广泛采用。
Thomas Bytheway ([email protected]) 是剑桥大学计算机实验室的研究助理。 他的研究兴趣在于构建通用溯源系统，并探索查询和可视化技术。
Ripduman Sohan ([email protected]) 是剑桥大学计算机实验室可重复计算结构 (FRESCO) 项目的高级研究助理和联合负责人 (Co-PI)。 他之前曾从事存储、虚拟化、网络和节能计算方面的工作。
Margo Seltzer ([email protected]) 是哈佛大学工程与应用科学学院的 Herchel Smith 计算机科学教授。 她还是 Sleepycat Software 的联合创始人兼首席技术官，该公司是 Berkeley DB 的制造商，直到 Oracle 在 2006 年收购 Sleepycat。 她现在是 Oracle 实验室的架构师。
Andy Hopper ([email protected]) 是剑桥大学计算机技术教授、计算机实验室主任和大学评议会当选成员。 他的研究兴趣包括计算机网络、普适计算和传感器驱动的计算，以及使用计算机来确保地球的可持续性。
© 2014 1542-7730/14/0300 $10.00
最初发表于 Queue vol. 12, no. 3—
在 数字图书馆 中评论这篇文章
更多相关文章
Ethan Miller, Achilles Benetopoulos, George Neville-Neil, Pankaj Mehra, Daniel Bittman - 远内存中的指针
有效利用新兴的远内存技术需要考虑在父进程上下文之外操作丰富连接的数据。 正在开发中的操作系统技术通过公开诸如内存对象和全局不变指针之类的抽象来提供帮助，这些抽象可以被设备和新实例化的计算遍历。 这些想法将使运行在具有分离内存节点的未来异构分布式系统上的应用程序能够利用近内存处理来实现更高的性能，并独立扩展其内存和计算资源以降低成本。
Simson Garfinkel, Jon Stewart - 磨砺你的工具
本文介绍了我们在最初发布十年后更新高性能数字取证工具 BE (bulk_extractor) 的经验。 在 2018 年至 2022 年期间，我们将该程序从 C++98 更新到 C++17。 我们还进行了完整的代码重构并采用了单元测试框架。 必须经常更新 DF 工具，以跟上其使用方式的变化。 对 bulk_extractor 工具更新的描述可以作为应该做和可以做什么的示例。
Pat Helland - 自主计算
自主计算是一种业务工作的模式，它使用协作来连接领地及其使者。 这种模式基于纸质表格，已经使用了几个世纪。 在这里，我们解释了领地、协作和使者。 我们考察了使者如何在自主边界之外工作，并且在保持局外人身份的同时保持便利性。 我们还考察了如何启动、长时间运行并最终完成跨不同领地的工作。
Archie L. Cobbs - 持久性编程
几年前，我的团队正在进行一个商业 Java 开发项目，用于增强型 911 (E911) 紧急呼叫中心。 我们试图使用传统的 Java over SQL 数据库模型来满足该项目的数据存储需求，但感到沮丧。 在对项目的特定需求（和非需求）进行一些反思之后，我们深吸一口气，并决定从头开始创建我们自己的自定义持久层。
© 保留所有权利。