分散式詢問及監督系統（distributed querying and monitoring systems）主要被用於分散式資料如檔案或是紀錄的維護上。網路內的使用者可以自系統中查詢所需資料如總和或平均值，若同時將所有原始資料做傳遞及運算，將耗費相當大的網路頻寬及運算資源。於是，內網路聚集（in-network aggregation）技術被提出來降低分散式詢問及監督系統的負擔。然而，這個技術卻容易遭受如injection attack或pollution attack的安全威脅。過去的研究大多假設資料來源為可信任，並針對聚集架構進行安全性的研究。然而，我們認為聚集查詢結果應該在面對惡意攻擊者將錯誤資料置入資料串流進行聚集前，就應該具備強健的容錯能力。傳統上，一個強健的估計值（robust estimator）被定義為即使資料來源有誤時，亦能維持一定程度正確性的聚集結果。許多常見的強健估計值是建立在有序統計學（order statistics）上，因此，我們將重心放在內網路計算上之有序統計的可驗證技術。此技術的挑戰為在網路遭受惡意團體介入聚集程序時，仍能確保聚集結果或近似結果的準確性。在本論文中，我們提出了 FM3 Proof Sketch 聚集協定( FM3 Proof Sketch Aggregation Protocol)，並將其整合進宣告式網路語言 Overlog。此外，我們也實做了一個用於監視點對點網路（peer-to-peer networks）健康狀況的雛型詢問系統，且為了證實我們的概念具有可行性，我們利用 FM3 Proof Sketch 聚集協定建制出一個兩層式的雛型PHI (Public Health for the Internet)系統並命名為"Prototypical PHI query"。同時，我們也設計了一系列的實驗來評估 FM3 聚集結果的狀況，來比較 FM3 與其他不具備驗證性之聚集技術的效能差異。據我們所知，目前的研究中，並沒有任何的機制能同時確保有序統計計算的效率及可檢驗性。而在此篇論文中，我們所提出的FM3 協定，不僅可以偵測行為不當的聚集者，更可以提供資料進入系統時，其結果的穩定性。此外，我們更證實聚集結果在有惡意資料的環境下，依然具備穩定性及定值誤差範圍內的近似結果。

Distributed querying and monitoring systems have been widely studied in recent years. These systems aim to maintain data sources, such as data sets or log files, and allow users to query over those data sources. When the data sources are highly related and users only care some statistic results, like the sum or the average, it is consumed to transmit all data sources via the network. To minimize the network consumption, in-network aggregation technique is proposed. However, this technique is subject to some known attacks, such as the injection attack and the pollution attack. Prior works only considered the settings that data sources are trusted while the network is not. We study the way to relax the limitation and guarantee the aggregate queries robust to malicious or faulty data sources (also called polluted data sources). We focus on verifiable techniques for in-network computation of order statistics. In this paper, we proposed the FM3 Proof Sketch aggregation protocol which can efficiently implement verifiable order statistics in-network aggregation. We also present a working distributed implementation of FM3 Proof Sketch, integrated into Overlog -- a declarative networking language. Moreover, we present an implementation of a prototypical query for peer-to-peer network health monitoring in this framework. As a proof-of-concept, we developed a two-level prototype PHI (Public Health for the Internet) system with FM3 Proof Sketch protocol named ``Prototypical PHI query'' and designed a series of experiments to evaluate the empirical effectiveness using FM3 scheme and to evaluate network performance by the overhead relative to a naive (non-verifiable) implementation. To our best knowledge, our mechanism is the first one that guarantees both the efficiency and verifiability of the order statistics computation.

[1] Praveen Yalagandula and Michael Dahlin, "A Scalable Distributed Information Management System," in ACM Special Interest Group on Data Communication Proceedings of the 2004 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), (Portland, Oregon, USA), pp. 379-390, ACM, Sep 2004.
[2] Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong, "Tag: A Tiny Aggregation Service for Ad-hoc Sensor Networks," in Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI), vol. 36, (Boston, Massachusetts, USA), pp. 131-146, ACM, Dec 2002.
[3] Ryan Huebsch, Brent N. Chun, Joseph M. Hellerstein, Boon Thau Loo, Petros Maniatis, Timothy Roscoe, Scott Shenker, Ion Stoica, and Aydan R. Yumerefendi, "The Architecture of PIER: an Internet-Scale Query Processor," in Proceedings of Second Biennial Conference on Innovative Data Systems Research (CIDR), (Asilomar, California, USA), pp. 28-43, Jan 2005.
[4] Yannis Kotidis, Vasilis Vassalos, Antonios Deligiannakis, Vassilis Stoumpos, and Alex Delis, "Robust Management of Outliers in Sensor Network Aggregate Queries," in Proceedings of the 6th ACM International Workshop on Data Engineering for Wireless and Mobile Access (MobiDE), (Beijing, China), pp. 17-24, ACM, Jun 2007.
[5] Sharmila Subramaniam, Themistoklis Palpanas, Dimitris Papadopoulos, Vana Kalogeraki, and Dimitrios Gunopulos, "Online Outlier Detection in Sensor Data using Non-parametric Models," in Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB), (Seoul, Korea), pp. 187-198, VLDB Endowment, Sep 2006.
[6] Bo Sheng, Qun Li, Weizhen Mao, and Wen Jin, "Outlier Detection in Sensor Networks," in Proceedings of the 8th ACM International Symposium on Mobile 53 Ad Hoc Networking and Computing (MobiHoc), (Montreal, Quebec, Canada), pp. 219-228, ACM, Sep 2007.
[7] David Wagner, "Resilient Aggregation in Sensor Networks," in Proceedings of the 2nd ACM Workshop on Security of Ad Hoc and Sensor Networks (SASN), (Washington DC, USA), pp. 78-87, ACM, Oct 2004.
[8] Bartosz Przydatek, Dawn Xiaodong Song, and Adrian Perrig, "SIA: Secure Information Aggregation in Sensor Networks," Journal of Computer Security: Special Issue on Security of Ad-hoc and Sensor Networks, vol. 15, pp. 69-102, Jan 2007.
[9] Yi Yang, XinranWang, Sencun Zhu, and Guohong Cao, "SDAP: A Secure Hop-by-Hop Data Aggregation Protocol for Sensor Networks," ACM Transactions on Information and System Security (TISSEC), vol. 11, Jul 2008.
[10] Haowen Chan, Adrian Perrig, and Dawn Xiaodong Song, "Secure Hierarchical In-network Aggregation in Sensor Networks," in Proceedings of the 13th ACM Conference on Computer and Communications Security, (Alexandria, Virginia, USA), pp. 278-287, ACM, Oct 2006.
[11] Minos N. Garofalakis, Joseph M. Hellerstein, and Petros Maniatis, "Proof Sketches: Verifiable In-network Aggregation," in Proceedings of IEEE 23rd International Conference on Data Engineering (ICDE), (Istanbul, Turkey), pp. 996-1005, Apr 2007.
[12] Philippe Flajolet and G. Nigel Martin, "Probabilistic Counting Algorithms for Data Base Applications," Journal of Computer and System Sciences, vol. 31, pp. 182-209, Sep 1985.
[13] Joseph M. Hellerstein, Tyson Condie, Minos N. Garofalakis, Boon Thau Loo,
Petros Maniatis, Timothy Roscoe, and Nina Taft, "Public Health for the Internet (ψ)," in Proceedings of Third Biennial Conference on Innovative Data Systems Research (CIDR), (Asilomar, California, USA), pp. 332-340, Jan 2007.
[14] Hsu-Chun Hsiao, Chih-Yuan Wang, Joseph M. Hellerstein, Wei-Chung Teng,
and Chin-Laung Lei, "Verifiable Order Statistics for Secure Aggregation," tech. rep., Technical Report No. UCB/EECS-2009-48, Berkeley, California, USA, Apr 2009.
[15] Graham Cormode and Marios Hadjieleftheriou, "Finding Frequent Items in Data Streams," in Proceedings of the VLDB Endowment, vol. 1, (Auckland, New Zealand), pp. 1530-1541, VLDB Endowment, Aug 2008.
[16] Boon Thau Loo, Tyson Condie, Joseph M. Hellerstein, Petros Maniatis, Timothy Roscoe, and Ion Stoica, "Implementing Declarative Overlays," in Proceedings of the Twentieth ACM Symposium on Operating Systems Principles (SOSP), (Brighton, United Kingdom), pp. 75-90, ACM, Oct 2005.
[17] Amit Manjhi, Suman Nath, and Phillip B. Gibbons, "Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams," in Proceedings of the 2005 ACM Special International Conference on Management of Data (SIGMOD), (Baltimore, Maryland), pp. 287-298, ACM, Jan 2005.
[18] Peter. J. Huber, Robust Statistics. Wiley, 1981.
[19] Frank R. Hampel, Elvezio M. Ronchetti, Peter J. Rousseeuw, and Werner A. Stahel, Robust Statistics - The Approach Based on Influence Functions. Wiley,
1986.
[20] Peter J. Rousseeuw and Christophe Croux, "Alternatives to the Median Absolute Deviation," Journal of the American Statistical Association, vol. 88, pp. 1273-1283, 1993.
[21] Boon Thau Loo, Tyson Condie, Minos Garofalakis, David E. Gay, Joseph M. Hellerstein, Petros Maniatis, Raghu Ramakrishnan, Timothy Roscoe, and Ion Stoica, \Declarative Networking: Language, Execution and Optimization," in Proceedings of the 2006 ACM Special International Conference on Management of Data (SIGMOD), (Chicago, Illinois, USA), pp. 97-108, ACM, Jun 2006.
[22] Anthony C. Davison and David V. Hinkley, Bootstrap Methods and Their Application. Cambridge University Press, Oct 1997.