今天要给大家推荐的论文是来自USENIX Security 2023的The Case for Learned Provenance Graph Storage Systems，由新泽西州立罗格斯大学安全实验室投稿完成并投稿。
概括
现有的存储溯源图并支持相关安全调查的数据库包括关系型数据库和图数据库。它们存储原始图数据，存在存储效率低下和查询效率低下的问题。本文介绍了一种基于深度神经网络（DNN）的溯源图（provenance graph）存储系统，名为Leonard。Leonard通过将溯源图转换为数值向量，可以使用很小的DNN模型来压缩表征大规模溯源图数据，节省存储空间。同时，Leonard可以建立索引并支持根据给定索引精准还原初始数据，从而支持数据的快速查询。本文展示了使用DNN模型代替传统数据库系统在溯源图存储以及安全调查任务上的可能性。实验结果表明，基于DNN的Leonard数据库系统与传统数据库存储系统相比有更高的存储效率和查询效率。
攻击调查与溯源图
溯源图（provenance graph）可以帮助分析系统活动。如图1所示，溯源图中的节点是系统主体/对象例如进程、文件和套接字，边代表两个节点之间的关系，例如系统调用类型read、write和connect。从检测到的攻击节点（payload）进行后向搜索可以找到攻击的源头（恶意网址abb.com）。前向搜索可以找到攻击的影响范围从而修复攻击损害。
存储溯源图的空间消耗通常很高。例如，Firefox中加载一个复杂CNN的网页，会发出近22,000个系统调用，这些调用创造了出处图中成千上万的节点和边。而且通常我们需要存储巨大的溯源图几个月甚至几年去支持潜在的安全调查。
当前存储系统缺点
目前已有的方法使用数据库（如关系型或图数据库）来存储溯源图。
关系型数据库将边和节点分别存储在两张不同的表中 (vertex table 和 edge table)。因为大型溯源图包含很多冗余信息，例如重复的文件名前缀和类型，关系型数据库的存储效率不高。此外，关系型数据库不能很好地支持图查询，在查询图时，我们往往需要迭代查询两张表，包含大量 IO 操作。
虽然图数据库对图数据提供更好的支持，但同样的，图数据库存储包含大量冗余的原始数据，导致存储效率低下。将整张大溯源图加载到内存中几乎不可能，因此一般的查询操作也会导致较高 IO 负载。
基于DNN的存储系统
本文观察到，深度神经网络 (DNN) 本质上是数据的一种压缩表示，因此 DNN 可以将大量数据信息压缩为一个模型。基于此，本文为溯源图存储设计了基于 DNN 的数据库。其基本思想是将溯源图转换为数值向量，为点和边建立索引，然后DNN 使用索引记住溯源图，并能通过给定索引还原具体的点和边。
DNN 存储和查询
具体来说，Leonard首先将溯源图中的节点和边解耦表示为多条文本记录（A.1）。然后，对这些记录进行冗余内容缩减 (A.2)，以去除由单调递增/递减的值和重复的值引起的冗余。例如，使用时间戳与记录中最小时间戳的差值来代替原来的长串时间戳，从而节省空间。Lenrad对图建立索引 (A.3)，它将每个节点和边的 ID 作为主键。对于每条边，额外使用边的起始节点和结束节点的 ID（或其他额外信息）作为索引来加速搜索过程。
最后，Leonard将每条记录的主键(ID)作为 DNN 模型的输入，并训练模型迭代进行下一个字符预测任务来补全记录 (B-Training)。与传统模型训练不同，Leonard的训练目标是迫使模型过拟合来记住训练数据。在训练结束后，其对训练数据重新进行预测并且使用校正表记录下误预测的位置和正确答案来校正误预测 (B-Calibration)。
在查询时，例如给定一个节点溯源搜索，Leonard首先在索引中查询得到结果图中所有节点和边的ID。然后将每个ID作为模型输入，使用模型补全每条记录，最后返回具体的结果图。在这个过程中，误预测可以查询校正表进行修复。
实验结果总结
Leonard在12个数据集上的结果表明，相比传统关系型数据库Quickstep和Neo4j, Leonard使用25.9倍更少的空间，在99.6%的查询上Leonard都表现的更快。
结束语
本文提出了一个新颖的研究系统Leonard。它使用DNN作为出处的图存储系统，具有很高的存储效率和查询效率。但由于Leonard存储数据时需要在数据上进行训练和校正，存储的时间成本较高，使得目前Leonard只适用于对存储时间不敏感的冷存储任务如攻击调查。Leonard中用到的技术可以被推广到更多的数据类型（比如文本）的存储任务和更多通用存储场景中。这个过程中也面临许多困难。比如包括减少改善存储效率，支持复杂的数据操作和为特定领域的重新设计预处理的压缩规则。而且Leonard的更新操作效率较低（每当储存的数据发生变化时，模型将被重新训练）。在攻击调查场景中，溯源图是只能附加和无法篡改的，因此不存在更新问题。然而，低效的更新在其他情况下是个问题，比如在推荐系统中存储用户关系图。但是随着机器学习加速工具的出现，可以预见时间限制会逐渐变小从而使得在未来利用学习模型代替数据库系统是可行的。
论文下载：
https://www.usenix.org/conference/usenixsecurity23/presentation/dinghailun
原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2023-04-25 Leonard
