TAP Transparent and Privacy-Preserving Data Services + ARI: Attestation of Real-time Mission Executi_tap: transparent and privacy-preserving data servi

作者信息：

文章网址：https://www.usenix.org/conference/usenixsecurity23/presentation/reijsbergen

总结：实现了

1. (R1) Rich operations for multiple users.supports a rich set of operations  
2. (R2) Data privacy: user A只能获取到 user B 有限的信息。而且the server includes each prefix tree leaf,即不知道原始数据，只知道hash值。it only reveals the results of queries.
3. (R3a) Data integrity: server不能修改数据/Honest users monitor the inclusion of their data in each epoch.
4. (R3b)Transparency. 用户可以验证server的操作结果是否准确。即“ the service’s processing of the data is verifiable by users and trusted auditors.”
5. (R4) Efficiency.  computation, storage, and network costs at the server and the user’s client are small.

本文涉及到的一些核心 cryptographic primitives： hash function H；additively homomorphic； non-interactive zero-knowledge proof system；Merkle tree； prefix tree

作者提出以上方案的缺点：不能同时满足R1-R4的要求。

核心创新点："The key component of TAP is a novel tree data structure that supports efficient result verification, and use zero-knowledge range proofs to show that the tree is constructed correctly without revealing user data. "

涉及到四个角色：

该模型涉及主要需聚焦的是： focus on guaranteeing perfect transparency at the cost of revealing query results, which cannot be trivially linked to user iden- tities.

1. user:  Users send data to the server and issue queries on the aggregate data through a client.  verifying that her data is properly stored by the server and verifies that query results are computed correctly.。半可信的角色。
2. Server：  stores the data 、 maintains an ADS on top of the data、computes responses to user queries、 generates proofs for the responses. 所以存在布告栏的角色，杜绝server一家独大伪造证明。不可信的角色。不考虑和user直接的合谋collusion. 
3. Auditors:   verify that data is never modified or deleted, and that certain data has been sorted correctly.。有 large computation and network resources 就可以成为审计者。
4. Bulletin board：可以理解为区块链prevent equivocation， The server periodically publishes the digest of its ADS to an immutable bulletin board, e.g., a public blockchain. Users and auditors download the latest digests during monitoring, auditing, and query verification.
5. during monitoring, auditing, and query verification"。可信的角色。conduct a comprehensive evaluation of TAP, and compare it against two state-of-the-art baselines, namely IntegriDB and Merkle, showing that the system is practical at scale.

居于树的结构实现以上功能：总结这棵树的功能：（1）by storing cryptographic commitments instead of raw data. （2）TAP’s Merkle tree structure ensures data integrity and allows users to verify the correctness of a broad range of queries。 （3）by generating Merkle proofs and zero-knowledge range proofs for the commitments’ underlying values.

The prefix tree is stored in memory； do not keep the Merkle sum trees in memory except for their root hashes。

如何把table转化成一颗tree.

粉色节点组成的树叫做 a Merkle prefix tree；蓝色节点组成的树叫做sorted Merkle sum trees。The prefix tree存储在memory中，the full table is stored in a SQL database。

(1) 节点00的

1. key：a unique combination of values of the Time and Type attributes，结果记作s；
2. value： the root hash of a sorted Merkle sum tree

(2) sorted sum tree: 

1. 叶子节点存储： commitments，hash, l=1. 其中，the server generates a random seed ri for each row i and stores it as a new attribute Seed . ri之后也会被发送给user,用于之后的verify.
2. 内部节点 A...F：c,h,l；li:  the number of leaves in the subtree rooted at the node；hi: the leaf’s hash

 注意：the initial digest  : the hash of the Merkle prefix tree root.这个值会被送到the bulletin board

各种操作做一个简单的概述：

1. Look-up： The user can search for the value v tied to her ID and seed for a given specific Time attribute t . 用户一句时间属性t、自己的ID、节点对应的值v得到一个搜索结果。server成功完成搜索操作之后，生成一个proof，v代表搜索结果。pie1是为基于the prefix tree产生的一个 the Merkle inclusion proof； pie2是基于the Merkle sum tree （具体就是基于commitment C(v,r)）产生的另一个 inclusion proof 。
2. Range cover： returns the set of prefix nodes that cover all entries in the specified range. 
3. Sum/Count/Average/Standard Deviation . 基于the child hash, commitment, leaf counts三个值能得到root节点的hash值，也就是digest，从而实现验证。

4. Auditing: the auditor如何实现审计： auditor要求验证时间t内的结果，server会根据t把这些leaf nodes筛选出来，然后auditor会执行树的重构。the root of the tree at time t can be rebuilt from the hashes in these nodes. 具体过程和[18]相同。 reveals the prefix tree and the commitments in the sum trees。这些值都不是敏感数据。

涉及到的证明transparent的几种类型的proofs: 

1. inclusion and non-inclusion proofs ( look-up queries)
2. inclusion and completeness proofs (sum querie,用到了同态加密)
3.  zero-knowledge range proofs (min, max, and quantile)不同的操作产生的proof内容不同。

该文参考的[30]中使用的NIZK算法实现：message +randomness

总结整个操作以及验证操作的流程：

1.  server初始化生成系统参数Ptap, 全局私钥SK ks, public verificication state表明验证状态的一个值Delta0。
2. ：基于系统参数和私钥，为用户i在t轮epoch生成秘密值rit.
3. ：user发起query, server执行query, 基于query类型QType, 系统参数、最新验证状态Delta_t-1、以及query的内容query message Mit（比如说要求insert，就需要把insert的内容附上）实现。输出query的结果，以及相关的proof πit, 被更新的状态值Deltat. 
4. 用户做验证操作。
5. auditor验证验证状态是否正确更新。

总结：最后验证通过的标准包括两种Verify() = 1 + EpochCheck() =1

关于文章使用的commitments and zero-knowledge range proofs的具体算法来自[10]Bulletproofs:

总结：对本文只掌握了大概，还没掌握的一点是为什么有的操作只是对比hash值，有的就需要用NIZK做保护。感觉这个和算法中透露的信息的privacy有关，需要更仔细的研究对应的算法才行。

CPS: cyber-physical systems

RMEI: Real-time Mission Execution Integrity 。具体的实现场景比如说：House Alarm (HA), Oxygen Concentrator (氧气浓缩器OC), and open Syringe Pump (开式注射泵SP)；autopilot

存在的一些正对system time的时间攻击： “ skip the function camera.update(), which leads the task update_GPS() to finish earlier.”

首先对比critial CPS和RMEI/real-time CPS的场景区别：常规的“remote attestation often focus on proof of correct execution that can detect control-flow and data-flow-related violations”，但是这适合于common IoT场景，不适用于autonomous real-time CPS。因为后一种场景更侧重：

1. “Continuous Measurement on the Mission (Operations) Integrity is Important：”即实时任务需要边执行任务边检测攻击，而不是最后执行一次简单的验证，因为它更注重过程是否成功执行。
2. “Temporal Property is also Important: ”关于时间主要检测的是：task completion latency and jitter，即需要在deadline内完成验证且信号稳定. 其次，更重要的是，把各个部分解耦的主要原因之一是：“strike the balance between the fidelity of the program behavior and real-time performance.”这些部件之间memory controller or software instrumentation隔离。

监测的数据包括3部分：（1）重要部件里的数据和控制流；各个部件之间转化时的记录信息；时间值。这些measurements内容通过policy实现实现。（control and data flow + transfers among the compartments + timestamp of each compartment transfer.）

ARI：Attestation of Real-time mission execution Integrity

1）Policy Generation: 系统设计者"software developers can specify every option for each compartment"或者"Users who are not familiar with the target software can use the built-in policies for compartmentalization and critical functions/variables annotation"。策略内容指的是什么：

1. 指定一个如何区分软件的策略 compartmentalize a software."Expert users can write a script to fully specify how compartments should be generated as well as the granularity of measurement on the program behaviors". 举例说明可以实现的一些策略类型： File-name-based or module-based built-in partition policy； Controller-based or peripheral-based(次要的) partition policy 。
2. 指定一个区分program events类型的策略，类型可能是control flow events, value-based data flow protection, execution timing, etc..

实验部分测试的policy包括：

1. Compartmentalization Policy：eripheral-based (peri.) or controller-based (cont.) policies groups functions based on the peripheral the code is operating on or the controller the code belongs to. File-based (file), operation-based (oper.), and module-based (modu.) compartmentalization policies group functions based on the file they belong to, the operations they support, and the
2. module they are in respectively, which are applied to smaller applications.
3. Critical Compartments and Variables:  举例fail-safe ,attitude for ArduCopter.

实验部分举例说明测试的内容：在Arducopter上测试的数据从整体上来看还是很仔细的。

结论： both runtime and memory overhead increase as the number of compartments increases。The increased runtime overhead is caused by the increased inter-compartment communications and data accesses。 The memory overhead is mainly caused by inter-compartment communication trampolines, stack redzones, and stub wrappers.

2) Compartment Generation and Labeling: ARI机制会自动把不同的software进行分类，然后给予标签"ARI automatically partitions the software into different compartments and then labels their criticality"。基于分类policy, 会把 the program分成很多子图，内核的分类依据是local data dependencies本地数据的依赖性。

3) Compartment Isolation:  enforce strong isolation between measured (critical/secure) and unmeasured (non-critical/non-secure) compartments. 该场景不适用于hardware platforms实现隔离的原因：作者提出的弊端是：（1）在CPS场景下，硬件各种各样的；（2）需要剥夺一部分对内容的高访问权限，这对real-time CPS场景是昂贵的（涉及到context switches）. 解决方案： software fault isolation (SFI) [22] is used to enforce compartmentalization in ARI.

（“软件故障隔离（Software Fault Isolation），它可以监视客户端程序，确保其不能够在它赋予范围之外进行写操作，在.NET中也采用了此种技术。”）目前常见软件保护技术概述_基于软件技术的软件安全保护技术有_顺其自然~的博客-CSDN博客

“SFI 是将代码限制在自己的代码块中。比如两个domainA 和B，A是trust, B是untrust, SFI就是防止B的代码跳转到A中，从而防止恶意攻击。
CFI主要是跳转的是有效地址，采用一种是CFG的技术，检查每次跳转的是不是符合CFG规定的地址。”（原文链接：https://blog.csdn.net/sploving/article/details/4533386）在本文中，SFI,CFI被理解为两种用于保护the destination of data access and control flow transfer instructions的方法。

“沙箱技术按照安全策略来限制程序对系统资源的使用，进而防止其对系统进行破坏，其有效性依赖于所使用的安全策略的有效性。沙箱技术按照安全策略来限制程序对系统资源的使用，进而防止其对系统进行破坏，其有效性依赖于所使用的安全策略的有效性。”Sandbox（用于安全的运行程序的机制）_百度百科 (baidu.com)

３）Real-time Attested Event Measurement：

1. Measurement of Inter/Intra Compartment Flows: only the inter-compartment  control flow　（CF）events and critical　intra-compartment CF events are recorded by default

４）Verification on the Measurement

主要通过mission re-execution实现inter-compartment control transfers + intra-critical-compartment indirect jumps + policy-specified variable values + critical compartment execution timing during the verification phase. 用户可能只会选择其中一部分继续验证。其两个的目的是against the offline generated CFG。

1. re-execution主要用于测试：Forward control flow and temporal measurement。
2.  comparing hash value:  Backward control flow
3. Critical variables: comparing expected value to recording from critical variable instrumentation.

 verification实现基于Capstone：Capstone是一个反汇编框架，提供了一个简单、轻量级的API接口，可透明地处理大多数流行的指令体系，包括x86/x86-64、ARM及MIPS等。Capstone支持C/C++和Python，并且可以在很多操作系统上运行。“C++ 基于Capstone实现反汇编器 - N3ptune - 博客园 (cnblogs.com)”

PDG: program dependency graph 

本文作者想实现的效果： integrity and timeliness of an autonomous CPS。即对内容做及时的完整性验证/设计了一个模型，叫做ARI， which is a policy-guided real-time mission execution integrity attestation system. 总结来讲，就是坚持程序行为在程序执行和时间属性上是否违规program behavior violations。

涉及到的核心概念/背景：Real-time Mission（即在规定时间内需要给出/得到反馈的任务）

背景知识：

了解什么是Remote Attestation:存在一个 a remote verifier，帮助实现可靠的内容完整性认证。目前大部分远程认证是静态的static, 最近有一些模型开始涉及verify  the runtime properties. 但帮助实现动态认证的 Real-time Autonomous CPS系统存在的几个问题：（1）针对时间属性，存在延迟攻击latency attack ，时间伪造攻击 jitter attack. (2) 在实际情况中，对Real-time CPS的需求是能够自动执行一些过程，比如说根据实际情况收集数据等。

区别于别的验证系统，本文的系统“is decomposed into multiple loosely coupled logical compartments”，各个部件之间“are isolated using either memory controller or software instrumentation”。

Compartmentalization隔离：这部分用于manipulate program on the PDG。 结果是 users can easily find the target functions or variables while traversing the PDG。 实现的是软件级别的隔离isolate different functionalities of the system。三中隔离内容：

1. Control Flow Isolation:  from non-critical compartments to critical compartments are measured.
2. Data Flow Isolation:  we adapt the value-based data flow protection technique [5], metadata +　critical variables．＂ ARI has to use address masking to create multiple
   compartments while facilitating access to shared memory.＂
3. Stack Isolation:  isolate stack between different　compartments.

贡献：

ARI实现的是selective attestation of mission integrity，这通过 a policy-based approach实现。更具体的讲，