中文摘要：

随着key-value存储系统的广泛使用,越来越多的研究开始关注分布式系统中的可信问题,其中一个重要的问题是,如何在系统被入侵或者管理员配置错误并运行一段时间后,检测出受污染的数据,从而可以在恢复错误数据的同时保留系统的合法更新.文中提出了一种基于key-value存储系统的错误污染检测方法,该方法允许在客户端不可信的前提下,检测客户端之间的污染扩散.文中设计了一种基于各服务器逻辑时钟的向量时钟,该时钟以用户关联操作为更新规则,记录了跨服务器的读写请求逻辑关系,用以进行错误污染跟踪;同时为了减少大规模系统中污染检测的开销,基于该向量时钟,文中进一步提出了一种在分布式系统中由操作序列构成有向无环图的污染分析方法.基于广泛使用的Voldmort key-value系统,文中实现了一个错误污染检测系统,Tracker Store.在集群测试环境下,文中对引入新的检测系统后产生的额外延迟开销进行了测试.

英文摘要：

With the widely adoption of key-value system, there have been many researches on reliability of distributed systems. One of the most important problems is the detection of taint data caused by legal user who has accessed untrustworthy data after intrusions by hackers or miscon- figurations by administrators, which enables preserving legitimate data while recovering taint data. This paper has proposed a mechanism for taint tracking based on key-value store, in the case where clients are not trustable. The vector clock based on logical clocks on servers is used to track relationships between cross-server accesses. Furthermore, in order to decrease the overhead incurred by the new system, this paper has explored a mechanism to construct DAG（Directed Acyclic Graph） s with operation sequences under distributed environment. A taint tracking system called Tracker Store is implemented upon the Voldemort key-value system, and overhead on read latency is evaluated on the new system.