论文主要是识别execution path。主要通过对系统调用的拦截实现+一些时序空间关系重构。

论文的核心目标是capture the complete end-to-end execution path of processing an individual request among all involved components of the platform。为此有几个挑战

一个线程可能同时为多个request提供服务，在多请求并发的情况下，我们应该确定线程处理每个单独请求的执行段（细粒度，如系统调用），并将这些段正确地链接到线程的完整执行程序中
在服务计算的许多场景中，请求的处理会穿越多个线程、进程、组件甚至计算机节点，因此我们应该在这些分布式部分中识别该请求处理的执行段，并将它们正确地连接起来
我们应该在源代码不可用的情况下解决前两个挑战

REP Construction

分析了服务请求处理的7种情况

在线程中继续执行。
当前线程创建另一个线程，并将请求的处理传递给新线程。当前的线程可以停止处理（例如，睡眠），或者继续处理这个请求。
当前进程fork一个进程，并将处理该请求的工作交给新的进程。当前进程可以停止或继续处理这个请求。
当前进程/线程向其他进程/线程发送一个消息，这个进程/线程可能在同一台机器上，也可能在另一台机器上。然后后一个进程/线程开始处理该请求。在这种情况下，网络通信和其他类似的机制，如管道，都包括在内。当前进程/线程可以停止或继续处理这个请求。
当前进程/线程使用某些IPC(Inter-Process Communication)机制，如进程等待、线程连接、信号、锁定/解锁、信号灯等，使请求的处理与另一个现有进程/线程同步。
当前进程/线程将请求（或其中间状态）保存在一个消息队列中。然后一个不同的进程/线程从消息队列中拿起该请求（或中间状态）并开始处理。
当前进程/线程使用共享内存、共享变量或映射设备将请求的处理传递给另一个现有的进程/线程。

通过观察服务请求的执行（和上面的场景），我们看到执行由以下序列组成：......-事件-线程执行-事件-线程执行-......，其中事件表示一个系统调用（或封装系统调用的LIBC调用），执行相关操作，线程执行表示一个线程在一个事件和其连续的事件之间连续执行。从序列中去除线程执行后，执行过程就被表示为序列 ... - 事件 - 事件 - ....

被追踪的分布式系统的每个节点（部署在容器、虚拟机或物理机内）上的 REPAgent 拦截封装那些感兴趣的系统调用的 LIBC 调用并生成事件。这些事件被上传到中央控制器进行event linking。

Event Generation

通过LD_PRELOAD机制拦截节点的LIBC调用。拦截的写在表1里了。

Event Linking

一共总结了五种情况。

第4个场景中的线程/进程之间通信的因果关系。 REPAgent在被拦截的发送呼叫的每个发送消息中插入一个唯一的ID，称为MSG_ID（MSG_ID的一部分是UUID，以确保其唯一性）。然后接收方的REPAgent从每个被拦截的recv呼叫的接收消息中提取该MSG_ID。这个MSG_ID是事件链接信息的一个属性。对于任何recv事件，其前身是具有相同MSG_ID的发送事件。

在场景1和其他场景中，同一线程内的时间继承性（例如，在异步消息模式下，线程在发送消息后继续处理请求）。 也就是利用时间关联将事件连在一起。一个挑战是如何排除那些不参与处理当前请求的事件。解决方法是利用MSG_CTX_ID来group those local events that are related to the same individual message。 MSG_CTX_ID被定义为从发送或接收一个消息（事件A）到发送或接收下一个消息（事件B）的连续计算的唯一标识。沿着请求的执行，事件A和事件B之间的所有事件都有相同的MSG_CTX_ID。

如果事件A是一个recv事件，一个新的MSG_CTX_ID被创建，并为事件A和A之后（和B之前）的那些事件做标记；
如果事件A是一个send事件，为了事件缝合的目的，事件A仍然用旧的MSG_CTX_ID做标记，并为A之后（和B之前）的那些事件创建一个新的MSG_CTX_ID。

情景2和3中线程创建和进程创建的因果关系。 线程/进程创建事件的调用信息具有由调用返回的新创建的线程/进程的ID。因此，如果一个事件是一个线程/进程的第一个事件，我们就会搜索那些线程/进程创建事件，并确定其预测。

线程间同步的因果关系。 事件的链接取决于具体的同步机制。对于每一种同步机制，我们都定义了其特定的因果关系识别方法。

线程/进程之间通过数据依赖的因果关系。 一个线程中写入数据的事件是另一个线程中读取写入值的事件的前提。如果数据的写入/读取不是通过系统调用，而是通过直接的内存访问（例如共享内存、共享变量），那么紧接着写入的事件是pred事件，紧接着读取的事件是 succ事件。然而，通过利用许多标准队列协议和中间件中的某些ID，我们仍然能够在某些情况下识别数据依赖关系。这种ID包括消息ID、工作ID、会话ID等。例如，在Apache ActiveMQ中，每个消息头都有一个唯一的消息ID；在Hadoop和Spark中提交和执行的每个作业都有一个作业ID。我们实施的 REPTrace 工具仅在存在此类 ID 时识别 5 类关系。

REP Representation

有向无环图。

ESSENTIAL PROCESSING OF REPS FOR KNOWLEDGE EXTRACTION

两个或多个规则适用时，某些事件有多个pred。我们将多pred链接仲裁为单pred，将DAG转换为事件树

Data pre-processing

类型3的规则 > 类型5的规则 > 类型4的规则 > 类型2的规则 > 类型1的规则。

我们对请求执行路径的数据预处理中，一个重要的任务是合并跟踪事件，使相同模式的事件只由一个副本代表，以便进一步分析。我们利用[46]中的一个经典的字符串模式算法来进行修剪。

Component Identification

这个操作模块在处理给定的请求时识别分布式系统的组件列表。识别组件是因为一个组件可能有多个进程/线程，为了人类对系统的理解，最好是在组件层面而不是在进程/线程层面了解相互作用。从事件树到process树的转换是通过从树上删除所有与process操作无关的事件来完成的。

Component Communication Identification

创建了请求处理中分布式服务组件的静态结构/架构的整体视图（结构视图）和请求处理中组件的深度交互视图（动态行为视图），从REP的开始到路径的结束。

REPTRACE-BASED ANOMALY DETECTION

REPTrace可被利用于服务请求处理的异常检测。基于REptrace的异常检测方法，由两个阶段组成：训练阶段和检测阶段。其基本思想是，在训练过程中从REP中构建几个有限状态自动机（FSA），然后将请求处理的运行时行为与FSA进行比较以检测异常。